Gaussian bounds for noise correlation of functions

DOI10.1007/s00039-010-0047-xzbMath1205.60051arXivmath/0703683OpenAlexW1973898585WikidataQ93585254 ScholiaQ93585254MaRDI QIDQ2379368

Elchanan Mossel

Publication date: 19 March 2010

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

invariancevotinghardness of approximationdiscrete harmonic analysisGaussian isoperimetric inequalities

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Large deviations (60F10) Asymptotic enumeration (05A16) Social choice (91B14)

Related Items

Noise-stability and central limit theorems for effective resistance of random electric networks, Approximating CSPs Using LP Relaxation, A query efficient non-adaptive long code test with perfect completeness, Probabilistic view of voting, paradoxes, and manipulation, Global and fixed-terminal cuts in digraphs, Nonlocal Games with Noisy Maximally Entangled States are Decidable, A quantitative Arrow theorem, Hypercontractivity for global functions and sharp thresholds, Multidimensional limit theorems for homogeneous sums: A survey and a general transfer principle, Secure non-interactive simulation from arbitrary joint distributions, A sprinkled decoupling inequality for Gaussian processes and applications, Forbidden intersections for codes, Noise correlation bounds for uniform low degree functions, On arithmetic progressions in symmetric sets in finite field model, $(2+\varepsilon)$-Sat Is NP-hard, The probability of intransitivity in dice and close elections, Invariance principles for homogeneous sums: universality of Gaussian Wiener chaos, A Characterization of hard-to-cover CSPs, Unnamed Item, The correct exponent for the Gotsman-Linial conjecture, Noise stability and correlation with half spaces, Maximally stable Gaussian partitions with discrete applications, Dimension Reduction for Polynomials over Gaussian Space and Applications, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Gaussian bounds for noise correlation of resilient functions, Simultaneous max-cut is harder to approximate than max-cut, The Quest for Strong Inapproximability Results with Perfect Completeness, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Hardness of Rainbow Coloring Hypergraphs, An Improved Dictatorship Test with Perfect Completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation resistant predicates from pairwise independence
• Noise stability of functions with low influences: invariance and optimality
• Quick approximation to matrices and applications
• The jackknife estimate of variance
• Inequalities in Fourier analysis
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Gowers uniformity, influence of variables, and PCPs
• Conditional hardness for approximate coloring
• On measures of dependence
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• The importance of being biased
• On the power of unique 2-prover 1-round games
• A Random Voting Graph Almost Surely has a Hamiltonian Cycle when the Number of Alternatives is Large
• Limit Theorems for Multilinear Forms and Quasipolynomial Functions
• Gaussian Hilbert Spaces
• Hypercontractivity of simple random variables
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Social Indeterminacy
• Das statistische Problem der Korrelation als Variations‐ und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung
• Hardness amplification within NP
• A remark on quadrant normal probabilities in high dimensions