Gowers uniformity, influence of variables, and PCPs

DOI10.1145/1132516.1132519MaRDI QIDQ2931365zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

probabilistically checkable proofslinearity testinfluence of variables

Mathematics Subject Classification ID

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)

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

Cited in

(8)

• Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
• Gaussian bounds for noise correlation of 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
• A self-tester for linear functions over the integers with an elementary proof of correctness
• Gowers Uniformity, Influence of Variables, and PCPs
• Noise correlation bounds for uniform low degree functions

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)