Article

Gowers uniformity, influence of variables, and PCPs

Authors:

Alex Samorodnitsky,

Luca TrevisanAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 11 - 20

https://doi.org/10.1145/1132516.1132519

Published: 21 May 2006 Publication History

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, Michael O. Rabin, and Madhu Sudan. Linear-consistency testing. Journal of Computer and System Sciences, 4(62):589--607, 2001.

Digital Library

[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]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Journal of the ACM, 45(3):501--555, 1998. Preliminary version in Proc. of FOCS'92.

Digital Library

[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]

S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70--122, 1998. Preliminary version in Proc. of FOCS'92.

Digital Library

[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]

M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCP's and non-approximability - towards tight results. SIAM Journal on Computing, 27(3):804--915, 1998. Preliminary version in Proc. of FOCS'95.

Digital Library

[8]

M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549--595, 1993. Preliminary version in Proc. of STOC'90.

Digital Library

[9]

Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.Sivakumar. On the hardness of approximating multicut and sparsest-cut. In Proceedings of the 20th IEEE Conference on Computational Complexity, 2005.

Digital Library

[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, 48(4):798--859, 2001.

Digital Library

[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 and Avi Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms, 22(2):139--160, 2003.

Digital Library

[22]

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 423--432, 2004.

Digital Library

[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. In Proceedings of the 34th ACM Symposium on Theory of Computing, pages 767--775, 2002.

Digital Library

[25]

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 146--154, 2004.

Digital Library

[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 and Dana Ron. Testing polynomials over general fields. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pages 413--422, 2004.

Digital Library

[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 Khot and Nisheeth Vishnoi. The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into 1. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 53--62, 2005.

Digital Library

[30]

Alex Samorodnitsky. Hypergraph linearity and quadraticity tests for boolean functions. Manuscript, 2005.

[31]

Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 191--199, 2000.

Digital Library

[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. In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 453--461, 2001.

Digital Library

[34]

Luca Trevisan. Inapproximability of combinatorial optimization problems. Technical Report TR04-065, Electronic Colloquium on Computational Complexity, 2004.

[35]

Vijay Vazirani. Approximation Algorithms. Springer, 2001.

Digital Library

Cited By

Hegyvári N(2024)Estimation of function's supports under arithmetic constraintsAnalysis Mathematica10.1007/s10476-024-00058-1Online publication date: 29-Oct-2024
https://doi.org/10.1007/s10476-024-00058-1
Hatami PTulsiani MCzumaj A(2018)Approximate local decoding of cubic reed-muller codes beyond the list decoding radiusProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175313(663-679)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175313
Engebretsen LHolmerin J(2018)More efficient queries in PCPs for NP and improved approximation hardness of maximum CSPRandom Structures & Algorithms10.5555/1458645.145864733:4(497-514)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.5555/1458645.1458647
Show More Cited By

Index Terms

Gowers uniformity, influence of variables, and PCPs
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Gowers Uniformity, Influence of Variables, and PCPs

We study the relation of query complexity and soundness in probabilistically checkable proofs (PCPs). 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 ...
Combinatorial PCPs with Efficient Verifiers

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated ...
Languages with efficient zero-knowledge PCPs are in SZK
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
529
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hegyvári N(2024)Estimation of function's supports under arithmetic constraintsAnalysis Mathematica10.1007/s10476-024-00058-1Online publication date: 29-Oct-2024
https://doi.org/10.1007/s10476-024-00058-1
Hatami PTulsiani MCzumaj A(2018)Approximate local decoding of cubic reed-muller codes beyond the list decoding radiusProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175313(663-679)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175313
Engebretsen LHolmerin J(2018)More efficient queries in PCPs for NP and improved approximation hardness of maximum CSPRandom Structures & Algorithms10.5555/1458645.145864733:4(497-514)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.5555/1458645.1458647
Devadas SRubinfeld R(2016)A Self-Tester for Linear Functions over the Integers with an Elementary Proof of CorrectnessTheory of Computing Systems10.1007/s00224-015-9639-z59:1(99-111)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00224-015-9639-z
Mikhailyuk V(2013)Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction ProblemsAmerican Journal of Operations Research10.4236/ajor.2013.3202503:02(279-288)Online publication date: 2013
https://doi.org/10.4236/ajor.2013.32025
De AMossel E(2013)Explicit Optimal Hardness via Gaussian Stability ResultsACM Transactions on Computation Theory10.1145/25057665:4(1-26)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1145/2505766
De AMossel ENeeman JBoneh DRoughgarden TFeigenbaum J(2013)Majority is stablestProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488668(477-486)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488668
Huang SBoneh DRoughgarden TFeigenbaum J(2013)Approximation resistance on satisfiable instances for predicates with few accepting inputsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488666(457-466)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488666
Khot SSafra MTulsiani MKleinberg R(2013)Towards an optimal query efficient PCP?Proceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422458(173-186)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422458
Austrin PMossel E(2013)Noise correlation bounds for uniform low degree functionsArkiv för Matematik10.1007/s11512-011-0145-551:1(29-52)Online publication date: Apr-2013
https://doi.org/10.1007/s11512-011-0145-5
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents