Gaussian bounds for noise correlation of functions
From the abstract: ``In this paper we derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O'Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions. ``We present two applications of the new bounds to the theory of social choice. We show that Majority is asymptotically the most predictable function among all low influence functions given a random sample of the voters. Moreover, we derive an almost tight bound in the context of Condorcet aggregation and low influence voting schemes on a large number of candidates. In particular, we show that for every low influence aggregation function, the probability that Condorcet voting on \(k\) candidates will result in a unique candidate that is preferable to all others is \(k^{-1+o(1)}\). This matches the asymptotic behavior of the majority function for which the probability is \(k^{-1-o(1)}\).
- Gaussian bounds for noise correlation of resilient functions
- Noise correlation bounds for uniform low degree functions
- Geometric influences. II: Correlation inequalities and noise sensitivity
- Noise stability of functions with low influences: invariance and optimality
- On the correlation of increasing families
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- A Random Voting Graph Almost Surely has a Hamiltonian Cycle when the Number of Alternatives is Large
- A remark on quadrant normal probabilities in high dimensions
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Approximation resistant predicates from pairwise independence
- Conditional hardness for approximate coloring
- Das statistische Problem der Korrelation als Variations‐ und Eigenwertproblem und sein Zusammenhang mit der Ausgleichsrechnung
- Gaussian Hilbert Spaces
- Geometric bounds on the Ornstein-Uhlenbeck velocity process
- Gowers uniformity, influence of variables, and PCPs
- Hardness amplification within NP
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 2034514 (Why is no real title available?)
- Hypercontractivity of simple random variables
- Inequalities in Fourier analysis
- Limit Theorems for Multilinear Forms and Quasipolynomial Functions
- Noise stability of functions with low influences: invariance and optimality
- On measures of dependence
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Quick approximation to matrices and applications
- Social Indeterminacy
- Szemerédi's regularity lemma revisited
- The importance of being biased
- The jackknife estimate of variance
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Noise stability and correlation with half spaces
- Maximally stable Gaussian partitions with discrete applications
- A quantitative Arrow theorem
- Noise correlation bounds for uniform low degree functions
- Invariance principles for homogeneous sums: universality of Gaussian Wiener chaos
- On arithmetic progressions in symmetric sets in finite field model
- The probability of intransitivity in dice and close elections
- Gaussian bounds for noise correlation of resilient functions
- Simple proof of hardness of feedback vertex set
- Noise-stability and central limit theorems for effective resistance of random electric networks
- Multidimensional limit theorems for homogeneous sums: a survey and a general transfer principle
- A query efficient non-adaptive long code test with perfect completeness
- Probability density functions for correlators with noisy reference signals
- Approximating CSPs using LP relaxation
- Bounds from noisy linear measurements
- Social choice, computational complexity, Gaussian geometry, and Boolean functions
- Lower bounds on same-set inner product in correlated spaces
- Product space models of correlation: between noise stability and additive combinatorics
- Geometric influences. II: Correlation inequalities and noise sensitivity
- The correct exponent for the Gotsman-Linial conjecture
- Global and fixed-terminal cuts in digraphs
- The quest for strong inapproximability results with perfect completeness
- Probabilistic view of voting, paradoxes, and manipulation
- Simultaneous max-cut is harder to approximate than max-cut
- Nonlocal Games with Noisy Maximally Entangled States are Decidable
- Dimension Reduction for Polynomials over Gaussian Space and Applications
- Hypergraph removal lemmas via robust sharp threshold theorems
- An improved dictatorship test with perfect completeness
- Hardness of rainbow coloring hypergraphs
- Rainbow coloring hardness via low sensitivity polymorphisms
- (2+)-Sat is NP-hard
- A characterization of hard-to-cover CSPs
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Hypercontractivity for global functions and sharp thresholds
- Secure non-interactive simulation from arbitrary joint distributions
- A sprinkled decoupling inequality for Gaussian processes and applications
- Forbidden intersections for codes
- On approximability of satisfiable k-CSPs. II
- On approximability of satisfiable k-CSPs. III
- A phase transition in Arrow's theorem with three alternatives
- Fitting metrics and ultrametrics with minimum disagreements
- On approximability of satisfiable k-CSPs: II
- An invariance principle for the multi-slice, with applications
- Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
- On approximability of satisfiable k-CSPs. I
- On approximability of satisfiable k-CSPs: V
- On the correlation of increasing families
This page was built for publication: Gaussian bounds for noise correlation of functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379368)
