New direct-product testers and 2-query PCPs

ABSTRACT

The "direct product code" of a function f gives its values on all k-tuples (f(x₁),...,f(x_k)). This basic construct underlies "hardness amplification" in cryptography, circuit complexity and PCPs. Goldreich and Safra [12] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [5] enabled for the first time testing proximity to this important code in the "list-decoding" regime. In particular, they give a 2-query test which works for polynomially small success probability 1/k^α, and show that no such test works below success probability 1/k. Our main result is a 3-query test which works for exponentially small success probability exp(-k^α). Our techniques (based on recent simplified decoding algorithms for the same code [15]) also allow us to considerably simplify the analysis of the 2-query test of [5]. We then show how to derandomize their test, achieving a code of polynomial rate, independent of k, and success probability 1/k^α. Finally we show the applicability of the new tests to PCPs. Starting with a 2-query PCP over an alphabet Σ and with soundness error 1-δ, Rao [19] (building on Raz's (k-fold) parallel repetition theorem [20] and Holenstein's proof [13]) obtains a new 2-query PCP over the alphabet Σ^k with soundness error exp(-δ² k). Our techniques yield a 2-query PCP with soundness error exp(-δ √k). Our PCP construction turns out to be essentially the same as the miss-match proof system defined and analyzed by Feige and Kilian [8], but with simpler analysis and exponentially better soundness error.

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: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
• 4: Irit Dinur, PCPs with small soundness error, ACM SIGACT News, v.39 n.3, September 2008 [doi>10.1145/1412700.1412713]
• 5: Irit Dinur , Elazar Goldenberg, Locally Testing Direct Product in the Low Error Range, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.613-622, October 25-28, 2008 [doi>10.1109/FOCS.2008.26]
• 6: Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem, SIAM Journal on Computing, v.36 n.4, p.975-1024, December 2006 [doi>10.1137/S0097539705446962]
• 7: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 8: Uriel Feige , Joe Kilian, Two-Prover Protocols---Low Error at Affordable Rates, SIAM Journal on Computing, v.30 n.1, p.324-346, 2000 [doi>10.1137/S0097539797325375]
• 9: Uriel Feige , Oleg Verbitsky, Error Reduction by Parallel Repetition—A Negative Result, Combinatorica, v.22 n.4, p.461-478, October 2002 [doi>10.1007/s00493-002-0001-0]
• 10: 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]
• 11: O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR-Lemma. ECCC, TR95-050, 1995.
• 12: Oded Goldreich , Shmuel Safra, A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem, SIAM Journal on Computing, v.29 n.4, p.1132-1154, Feb. 2000 to March 2000 [doi>10.1137/S0097539797315744]
• 13: Thomas Holenstein, Parallel repetition: simplifications and the no-signaling case, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250852]
• 14: Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets, Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.187-196, October 21-24, 2006 [doi>10.1109/FOCS.2006.13]
• 15: Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets , Avi Wigderson, Uniform direct product theorems: simplified, optimized, and derandomized, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374460]
• 16: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 17: Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
• 18: Dana Moshkovitz , Ran Raz, Two Query PCP with Sub-Constant Error, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.314-323, October 25-28, 2008 [doi>10.1109/FOCS.2008.60]
• 19: Anup Rao, Parallel repetition in projection games and a concentration bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374378]
• 20: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 21: Ran Raz, A Counterexample to Strong Parallel Repetition, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.369-373, October 25-28, 2008 [doi>10.1109/FOCS.2008.49]
• 22: Luca Trevisan, List-Decoding Using The XOR Lemma, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.126, October 11-14, 2003
• 23: Oleg Verbitsky, Towards the parallel repetition conjecture, Theoretical Computer Science, v.157 n.2, p.277-282, May 5, 1996 [doi>10.1016/0304-3975(95)00165-4]
• 24: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.80-91, November 03-05, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

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

General Terms:
Algorithms, Theory

Keywords:
PCP, direct products, parallel repetition, testing