Gowers uniformity, influence of variables, and PCPs

DOI10.1145/1132516.1132519zbMath1301.68137OpenAlexW1975810219MaRDI QIDQ2931365

Alex Samorodnitsky, Luca Trevisan

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132519

zbMATH Keywords

probabilistically checkable proofslinearity testinfluence of variables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Gaussian bounds for noise correlation of functions ⋮ A self-tester for linear functions over the integers with an elementary proof of correctness ⋮ Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm ⋮ Noise correlation bounds for uniform low degree functions ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

This page was built for publication: Gowers uniformity, influence of variables, and PCPs