Interpolation and approximation of sparse multivariate polynomials over GF(2)

A function f:{0, 1}n → {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 ≥n-[log2 t]-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 t-sparse functions is considered, in which case the approximating function may differ from f at a fraction ε of the space {0, 1}n. It is shown that O((t/ε) · n) evaluation points are sufficient for the (deterministic) ε-approximation of any t-sparse function, and that an order of (t/ε)α(t,ε) · log n points are necessary for this purpose, where α(t, ε)≥0.694 for a large range of t and ε. Similar bounds hold for the t-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the ε-approximation of any t-sparse function.