Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
From MaRDI portal
Publication:2472722
DOI10.1007/BF02773611zbMath1140.60007arXivmath/0410560OpenAlexW2163010692MaRDI QIDQ2472722
Oded Regev, Ryan O'Donnell, Jeffrey E. Steif, Elchanan Mossel, Benjamin Sudakov
Publication date: 22 February 2008
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0410560
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)
Related Items
On the round complexity of randomized Byzantine agreement, Quantum reverse hypercontractivity, On reverse hypercontractivity, Complete Minors in Graphs Without Sparse Cuts, Coin flipping from a cosmic source: On error correction of truly random bits, A quantitative Gobbard-Satterthwaite theorem without neutrality, Probabilistic view of voting, paradoxes, and manipulation, Secure non-interactive simulation: feasibility and rate, A quantitative Arrow theorem, Secure non-interactive simulation from arbitrary joint distributions, On the \(\Phi \)-stability and related conjectures, ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS, Hypercontractivity of Spherical Averages in Hamming Space, Geometric influences. II: Correlation inequalities and noise sensitivity, On percolation and ‐hardness, Maximally stable Gaussian partitions with discrete applications, On the probability of a rational outcome for generalized social welfare functions on three alternatives, Noise stability of functions with low influences: invariance and optimality, A tight quantitative version of Arrow's impossibility theorem, Dimension Reduction for Polynomials over Gaussian Space and Applications, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Second-order converses via reverse hypercontractivity, Common Information, Noise Stability, and Their Extensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Normal approximation - some recent advances
- Gibbs measures and phase transitions
- Inequalities in Fourier analysis
- Correlation inequalities on some partially ordered sets
- Boolean functions with low average sensitivity depend on few coordinates
- Discrete isoperimetric and Poincaré-type inequalities
- Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
- Influences of variables and threshold intervals under group symmetries
- The influence of variables in product spaces
- Derandomized graph products
- Boolean functions whose Fourier transform is concentrated on the first two levels.
- Uniform-distribution attribute noise learnability
- Fourier analysis for probabilistic communication complexity
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- The importance of being biased
- On the power of unique 2-prover 1-round games
- Global wellposedness of defocusing critical nonlinear Schrödinger equation in the radial case
- Every monotone graph property has a sharp threshold
- Coin flipping from a cosmic source: On error correction of truly random bits
- Some optimal inapproximability results
- Families of Non-disjoint subsets
- Noise sensitivity of Boolean functions and applications to percolation
