Learning sparse polynomials from random samples is a notorious problem in learning theory. We show that
if the coefficients are in general position we can learn such functions efficiently. We show how this problem
has applications on learning the structure of unknown graphs by observing the values of graph cuts. We
further discuss our on-going work on learning variable interactions (quadratic polynomials) very efficiently.
Our techniques are coding theoretic and boil down to solving noisy linear equations over a finite field.
Based on joint work with Murat Kocaoglu, Karthik Shanmugam, and Adam Klivans.