Gowers Uniformity, Influence of Variables, and PCPs
From MaRDI portal
Publication:5189548
DOI10.1137/070681612zbMath1185.68353arXivmath/0510264OpenAlexW2055711302MaRDI QIDQ5189548
Luca Trevisan, Alex Samorodnitsky
Publication date: 17 March 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0510264
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
GOWERS UNIFORMITY NORM AND PSEUDORANDOM MEASURES OF THE PSEUDORANDOM BINARY SEQUENCES ⋮ A query efficient non-adaptive long code test with perfect completeness ⋮ On the Gowers norms of certain functions ⋮ Unnamed Item ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Finite field models in arithmetic combinatorics -- ten years on ⋮ Energies and structure of additive sets ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Unnamed Item ⋮ An Improved Dictatorship Test with Perfect Completeness
