Sub-constant error low degree test of almost-linear size

ABSTRACT

Given a function f:F^m→F over a finite field F, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of constant dimension (e.g., lines, planes, etc.). The tester makes very few (probabilistic) queries to f and to A (say, one query to f and one query to A), and decides whether to accept or reject based on the replies.We wish to minimize two parameters of a tester: its error and its size. The error bounds the probability that the tester accepts although the function is far from a low degree polynomial. The size is the number of bits required to write the oracle replies on all possible tester's queries.Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). The error of the low degree tester is related to the soundness of the PCP and its size is related to the size of the PCP (or the length of the LTC).We design and analyze new low degree testers that have both sub-constant error o(1) and almost-linear size n^1+o(1) (where n=|F|^m). Previous constructions of sub-constant error testers had polynomial size [13, 16]. These testers enabled the construction of PCPs with sub-constant soundness, but polynomial size [13, 16, 9]. Previous constructions of almost-linear size testers obtained only constant error [13, 7]. These testers were used to construct almost-linear size LTCs and almost-linear size PCPs with constant soundness [13, 7, 5, 6, 8].

REFERENCES

• 1: 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]
• 2: 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]
• 3: S. Arora and M. Sudan. Improved low-degree testing and its applications. Combin., 23(3):365--426, 2003.
• 4: L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. In Proc. 31st IEEE FOCS, pages 16--25, 1990.
• 5: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007361]
• 6: Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060631]
• 7: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 8: Irit Dinur, The PCP theorem by gap amplification, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132553]
• 9: Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra, PCP characterizations of NP: towards a polynomially-small error-probability, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.29-40, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301265]
• 10: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 11: K. Ford. The distribution of integers with a divisor in a given interval. 2004.
• 12: Some improvements to total degree tests, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.190, January 04-06, 1995
• 13: 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
• 14: R. Hall and G. Tenenbaum. Divisors, volume 90 of Cambridge Tracts in Mathematics. Cambridge University Press, 1988.
• 15: D. Moshkovitz and R. Raz. Sub-constant error low degree test of almost-linear size. Technical Report TR05-086, ECCC, 2005.
• 16: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 17: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields; Computations on polynomials

General Terms:
Theory

Keywords:
locally testable codes, low degree testing, plane vs. point test, probabilistically checkable proofs