Low-degree tests at large distances

ABSTRACT

We define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. The tests have optimal or nearly optimal trade-offs between soundness and the number of queries.

A central step in our analysis of quadraticity tests is the proof of aninverse theorem for the third Gowers uniformity norm of boolean functions.

The last result implies that it ispossible to estimate efficiently the distance from the second-order Reed-Muller code on inputs lying far beyond its list-decoding radius.

Our main technical tools are Fourier analysis on Z₂ⁿ and methods from additive number theory. We observe that these methods can be used to give a tight analysis of the Abelian Homomorphism testing problemfor some families of groups, including powers of Z_p.

REFERENCES

• 1: N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, D. Ron, Testing low-degree polynomials over GF(2), RANDOM-APPROX 2003, pp. 188--199.
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 4: M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, M. Sudan Linearity testing in characteristic 2, IEEE Trans. Inform. Theory, vol. IT-42, 6, 1996, 1782--1795.
• 5: M. Ben-Or, D. Coppersmith, Personal communication to the authors of BLR, 1989.
• 6: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 7: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for unique games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132547]
• 8: Lars Engebretsen , Jonas Holmerin, Towards optimal lower bounds for clique and chromatic number, Theoretical Computer Science, v.299 n.1-3, p.537-584, 18 April 2003 [doi>10.1016/S0304-3975(02)00535-2]
• 9: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 10: Oded Goldreich , Madhu Sudan, Locally Testable Codes and PCPs of Almost-Linear Length, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.13-22, November 16-19, 2002
• 11: W. T. Gowers, A new proof of Szemeredi's theorem, GAFA Vol. 11(2001), pp. 465--588.
• 12: B. Green, Montreal notes on quadratic Fourier analysis, preprint, Mathematics ArXiv CA/0604089.
• 13: B. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, to appear.
• 14: B. Green, T. Tao, An inverse theorem for the Gowers U³ norm, Proc. Edin. Math. Soc., to appear.
• 15: G. Hast, Approximating Max kCSP - outperforming a random assignment by almost a linear factor, ICALP 2005, to appear.
• 16: B. Host and B. Kra, Nonconventional ergodic averages and nilmanifolds, Annals of Mathematics, 161(1):397--488, 2005.
• 17: J. Kahn, G. Kalai, and N. Linial, The influence of variables on boolean functions, FOCS 1988, pp. 68--80.
• 18: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 19: J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Amsterdam, North-Holland, 1977.
• 20: J. G. Oxley, Matroid Theory, New York, Oxford University Press, 1992.
• 21: I. S. Reed, A class of multiple error correcting codes and the decoding scheme, IEEE IT, vol. 4, 1954, pp. 38--49.
• 22: I. Z. Ruzsa, An analog of Freiman's theorem in groups, Asterisque 258, 199, pp. 323--326.
• 23: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 24: Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
• 25: Madhu Sudan, List Decoding: Algorithms and Applications, Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics, p.25-41, August 17-19, 2000
• 26: L. Trevisan, Parallel approximation algorithms by positive linear programming, Algorithmica 21(1):72--88, 1998.
• 27: Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276769]
• 28: T. Ziegler, Universal characteristic factors and Furstenberg averages, Journal of AMS 20, 2007, pp. 53--97.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
low-degree tests