About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Interpolation and approximation of sparse multivariate polynomials over GF(2)
Abstract
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.
Related
Conference paper
Compliance-as-Code for Cybersecurity Automation in Hybrid Cloud
Conference paper