Timezone: »

 
Oral
Sparse Polynomial Learning and Graph Sketching
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans

Wed Dec 10 06:50 AM -- 07:10 AM (PST) @ Level 2, room 210
in Oral Session 5 »
Let $f: \{-1,1\}^n \rightarrow \mathbb{R}$ 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 distribution on $\{-1,1\}^n$ that runs in time polynomial in $n$ and $2^{s}$ and succeeds if the function satisfies the \textit{unique sign property}: there is one output value which corresponds to a unique set of values of the participating parities. This sufficient condition is satisfied when every coefficient of $f$ is perturbed by a small random noise, or satisfied with high probability when $s$ parity functions are chosen randomly or when all the coefficients are positive. Learning sparse polynomials over the Boolean domain in time polynomial in $n$ and $2^{s}$ is considered notoriously hard in the worst-case. Our result shows that the problem is tractable for almost all sparse polynomials. Then, we show an application of this result to hypergraph sketching which is the problem of learning a sparse (both in the number of hyperedges and the size of the hyperedges) hypergraph from uniformly drawn random cuts. We also provide experimental results on a real world dataset.

Author Information

Murat Kocaoglu (Purdue University)
Karthikeyan Shanmugam (IBM Research, NY)
Alexandros Dimakis (University of Texas, Austin)
Adam Klivans (UT Austin)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors