Sparse Polynomial Learning and Graph Sketching

Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G. Dimakis +1

Let $f:\{-1,1{\}}^n$ be a polynomial with at most $s$ non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distributio…