| Testing low-degree polynomials over GF(2), booktitle (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥ 1 and a given real ɛ> 0, the algorithm queries f at O ( 1 ɛ + k4k) points. If f is a polynomial of degree at most k, the algorithm always accepts, and if the value of f has to be modified on at least an ɛ fraction of all inputs in order to transform it to such a polynomial, then the algorithm rejects with probability at least 2/3. Our result is essentially tight: Any algorithm for testing degree-k polynomials over GF (2) must perform Ω ( 1 ɛ + 2k) queries. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||