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(\frac{1}{\epsilon}+k4^k)\) 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 \(\Omega(\frac{1}{\epsilon}+2^k)\) queries.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. In: Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science, pp. 645–655 (1999)
Arora, S., Safra, S.: Improved low-degree testing and its applications. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 485–495 (1997)
Babai, L., Fortnow, L., Levin, L., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 21–31 (1991)
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1(1), 3–40 (1991)
Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: Proceedings of the Thirty-Sixth Annual Symposium on Foundations of Computer Science, pp. 432–441 (1995)
Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximation. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pp. 294–304 (1993)
Bellare, M., Sudan, M.: Improved non-approximability results. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pp. 184–193 (1994)
Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: 3CNF properties are hard to test. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing (2003) (to appear)
Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Derandomizing low degree tests via epsilon-biased spaces. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing (2003) (to appear)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47, 549–595 (1993)
Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. Journal of the Association for Computing Machinery, 268–292 (1996)
Friedl, K., Sudan, M.: Some improvements to total degree tests. In: Proceedings of the 3rd Annual Israel Symposium on Theory of Computing and Systems, pp. 190–198 (1995), Corrected version available online at http://theory.lcs.mit.edu/~madhu/papers/friedl.ps
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing/correcting for polynomials and for approximate functions. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 32–42 (1991)
Hall, M.: Combinatorial Theory. John Wiley & Sons, Chichester (1967)
Kasami, T., Lin, S., Peterson, W.W.: New generalizations of the reed-muller codes, part i: Primitive codes. IEEE Transactions on Information Theory, 189–199 (1968)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1977)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)
Sudan, M.: Private communications (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D. (2003). Testing Low-Degree Polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds) Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques. RANDOM APPROX 2003 2003. Lecture Notes in Computer Science, vol 2764. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45198-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-45198-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40770-6
Online ISBN: 978-3-540-45198-3
eBook Packages: Springer Book Archive