Noise correlation bounds for uniform low degree functions

DOI10.1007/S11512-011-0145-5zbMATH Open1296.68102arXiv0904.0157OpenAlexW1967553055MaRDI QIDQ1944763FDOQ1944763

Elchanan Mossel, Per Austrin

Publication date: 27 March 2013

Published in: Arkiv för Matematik (Search for Journal in Brave)

Abstract: We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by $delta$ are called $delta$-{em uniform}. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics. In our main result we show that $E[f_1(X_1^1,\mathrm{...},X_1^n)\mathrm{...}{f}_k(X_k^1,\mathrm{...},X_k^n)]$ is close to 0 under the following assumptions: 1. The vectors $(X_1^j,\mathrm{...},X_k^j):1leqjleqn$ are i.i.d, and for each $j$ the vector $(X_1^j,\mathrm{...},X_k^j)$ has a pairwise independent distribution. 2. The functions $f_i$ are uniform. 3. The functions $f_i$ are of low degree. We compare our result with recent results by the second author for low influence functions and to recent results in additive combinatorics using the Gowers norm. Our proofs extend some techniques from the theory of hypercontractivity to a multilinear setup.

Full work available at URL: https://arxiv.org/abs/0904.0157

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A new proof of Szemerédi's theorem
• 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
• On the power of unique 2-prover 1-round games
• On Certain Sets of Integers
• The true complexity of a system of linear equations
• Noise sensitivity of Boolean functions and applications to percolation
• Noise stability of functions with low influences: invariance and optimality
• Limit theorems for polylinear forms
• Gowers uniformity, influence of variables, and PCPs
• Approximation resistant predicates from pairwise independence

Cited In (5)

• Noise stability and correlation with half spaces
• Gaussian bounds for noise correlation of resilient functions
• Probability density functions for correlators with noisy reference signals
• On arithmetic progressions in symmetric sets in finite field model
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

This page was built for publication: Noise correlation bounds for uniform low degree functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944763)