Gowers uniformity, influence of variables, and PCPs
From MaRDI portal
Publication:2931365
DOI10.1145/1132516.1132519zbMath1301.68137MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A self-tester for linear functions over the integers with an elementary proof of correctness, Noise stability of functions with low influences: invariance and optimality, Noise correlation bounds for uniform low degree functions, Gaussian bounds for noise correlation of functions, Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
