Gowers uniformity, influence of variables, and PCPs

ABSTRACT

We return to the study of the relation of query complexity and soundness in probabilistically checkable proofs.We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most 2q/2^q+ε, for arbitrarily small ε>0. For values of q of the form 2^t-1, the soundness error is (q+1)/2^q+ε.Charikar et al. show that there is a constant c such that for every language that has a verifier of query complexity q, and a ratio of soundness error to completeness smaller than cq/2^q is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight.As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree Δ within a factor better than Δ/(log Δ)^c is Unique-Games-Hard for a certain constant c>0.Our main technical results are (i) a connection between the Gowers uniformity of a Boolean function and the influence of its variables and (ii) the proof that "Gowers uniform" functions pass the "hypergraph linearity test" approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

REFERENCES

• 1: Yonatan Aumann , Johan Håstad , Micheal O. Rabin , Madhu Sudan, Linear-consistency testing, Journal of Computer and System Sciences, v.62 n.4, p.589-607, June 2001 [doi>10.1006/jcss.2001.1747]
• 2: Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing low-degree polynomials over GF(2). In Proceedings of RANDOM-APPROX, pages 188--199, 2003.
• 3: 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]
• 4: Sanjeev Arora. How NP got a new definition: a survey of probabilistically checkable proofs. In Proceedings of the International Congress of Mathematicians, pages 637--648, 2002. Volume 3.
• 5: 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]
• 6: M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan. Linearity testing over characteristic two. IEEE Transactions on Information Theory, 42(6):1781--1795, 1996.
• 7: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 8: 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]
• 9: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 10: Irit Dinur and Shmuel Safra. On the hardness of approximating minimum vertex-cover. Annals of Mathematics, 162(1):439--486, 2005.
• 11: Lars Engebretsen and Jonas Holmerin. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. pages 194--205, 2005.
• 12: Uriel Feige. Approximation thresholds for combinatorial optimization problems. In Proceedings of the International Congress of Mathematicians, pages 649--658, 2002. Volume 3.
• 13: Timothy Gowers. A new proof of Szemèredi's theorem for progressions of length four. Geometric and Functional Analysis, 8(3):529--551, 1998.
• 14: Timothy Gowers. A new proof of Szemèredi's theorem. Geometric and Functional Analysis, 11(3):465--588, 2001.
• 15: Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. To appear in Annals of Mathematics. math.NT/0404188, 2004.
• 16: Ben Green and Terence Tao. An inverse theorem for the Gowers U3 norm. math.NT/0503014, 2005.
• 17: J. Håstad. Clique is hard to approximate within n1?ε. Acta Mathematica, 182:105--142, 1999.
• 18: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 19: Gustav Hast. Approximating Max kCSP - outperforming a random assignment with almost a linear factor. pages 956--968, 2005.
• 20: Bernard Host and Bryna Kra. Nonconventional ergodic averages and nilmanifolds. Annals of Mathematics, 161(1):397--488, 2005.
• 21: Johan Håstad , Avi Wigderson, Simple analysis of graph tests for linearity and PCP, Random Structures & Algorithms, v.22 n.2, p.139-160, March 2003 [doi>10.1002/rsa.10068]
• 22: Charanjit S. Jutla , Anindya C. Patthak , Atri Rudra , David Zuckerman, Testing Low-Degree Polynomials over Prime Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.423-432, October 17-19, 2004 [doi>10.1109/FOCS.2004.64]
• 23: J. Kahn, G. Kalai, and N. Linial The influence of variables on boolean functions. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 68--80, 1988.
• 24: 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]
• 25: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 26: Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2 ?- ε. In Proceedings of the 18th IEEE Conference on Computational Complexity, 2003.
• 27: Tali Kaufman , Dana Ron, Testing Polynomials over General Fields, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.413-422, October 17-19, 2004 [doi>10.1109/FOCS.2004.65]
• 28: Bryna Kra. The Green-Tao theorem on arithmetic progressions in the primes: an ergodic point of view. Bulletin of the AMS. To appear.
• 29: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 30: Alex Samorodnitsky. Hypergraph linearity and quadraticity tests for boolean functions. Manuscript, 2005.
• 31: 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]
• 32: Luca Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72--88, 1998. Preliminary version in Proc. of ESA'96.
• 33: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]
• 34: Luca Trevisan. Inapproximability of combinatorial optimization problems. Technical Report TR04-065, Electronic Colloquium on Computational Complexity, 2004.
• 35: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory

Keywords:
influence of variables, linearity test, probabilistically checkable proofs