Noise correlation bounds for uniform low degree functions
From MaRDI portal
Publication:1944763
DOI10.1007/s11512-011-0145-5zbMath1296.68102arXiv0904.0157MaRDI QIDQ1944763
Publication date: 27 March 2013
Published in: Arkiv för Matematik (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0904.0157
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
11B30: Arithmetic combinatorics; higher degree uniformity
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
On arithmetic progressions in symmetric sets in finite field model, Gaussian bounds for noise correlation of resilient functions, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- Noise stability of functions with low influences: invariance and optimality
- Limit theorems for polylinear forms
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- Gaussian bounds for noise correlation of functions
- The primes contain arbitrarily long arithmetic progressions
- Gowers uniformity, influence of variables, and PCPs
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- On Certain Sets of Integers
- The true complexity of a system of linear equations
- Noise sensitivity of Boolean functions and applications to percolation
- A new proof of Szemerédi's theorem