Gowers uniformity, influence of variables, and PCPs
DOI10.1145/1132516.1132519zbMATH Open1301.68137OpenAlexW1975810219MaRDI QIDQ2931365FDOQ2931365
Authors: 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
Recommendations
- Gowers Uniformity, Influence of Variables, and PCPs
- A point of view on Gowers uniformity norms
- A Guttman effect in PCA
- Influence in canonical variates analysis
- Uniform consistency in causal inference
- Multivariate coefficients of variation: comparison and influence functions
- Influence of uniform distribution samples on parameter estimation
- scientific article; zbMATH DE number 1782178
- Multivariate tests of uniformity
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (8)
- 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
- Noise correlation bounds for uniform low degree functions
- Noise stability of functions with low influences: invariance and optimality
- Gowers Uniformity, Influence of Variables, and PCPs
- A self-tester for linear functions over the integers with an elementary proof of correctness
- Gaussian bounds for noise correlation of functions
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
This page was built for publication: Gowers uniformity, influence of variables, and PCPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931365)
