Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$

Abstract

A function $f:\{ 0,1\} ^n \to \{ 0,1\} $ is called t-sparse if the n-variable polynomial representation of f over $GF(2)$ contains at most t monomials. Such functions are uniquely determined by their values at the so-called critical set of all binary n-tuples of Hamming weight $ \geqq n - \lfloor \log _2 t \rfloor - 1$. An algorithm is presented for interpolating any t-sparse function f, given the values of f at the critical set. The time complexity of the proposed algorithm is proportional to n, t, and the size of the critical set. Then, the more general problem of approximating 1-sparse functions is considered, in which case the approximating function may differ from f at a fraction $\varepsilon $ of the space $\{ 0,1\} ^n $. It is shown that $O(({t / \varepsilon }) \cdot n)$ evaluation points are sufficient for the (deterministic) $\varepsilon $-approximation of any t-sparse function, and that an order $(t / \varepsilon )^{\alpha (t,\varepsilon )} \cdot \log n$ points are necessary for this purpose, where $\alpha (t,\varepsilon ) \geqq 0.694$ for a large range of t and $\varepsilon $. Similar bounds hold for the t-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the $\varepsilon $-approximation of any t-sparse function.