Noise correlation bounds for uniform low degree functions

DOI10.1007/s11512-011-0145-5zbMath1296.68102arXiv0904.0157MaRDI QIDQ1944763

Elchanan Mossel, Per Austrin

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

Mathematics Subject Classification ID

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