Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality

DOI10.1007/BF02773611MaRDI QIDQ2472722zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E. Steif, Benny 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

zbMATH Keywords

inhomogeneous Markov chainsnon-interactive correlation distillation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: In this paper we study non-interactive correlation distillation (NICD), a generalization of the study of noise sensitivity of boolean functions. We extend the model to NICD on trees. In this model there is a fixed undirected tree with players at some of the nodes. One node is given a uniformly random string and this string is distributed throughout the network, with the edges of the tree acting as independent binary symmetric channels. The goal of the players is to agree on a shared random bit without communicating. Our new contributions include the following: 1. In the case of a k-leaf star graph, we resolve the open question of whether the success probability must go to zero as k goes to infinity. We show that this is indeed the case and provide matching upper and lower bounds on the asymptotically optimal rate (a slowly-decaying polynomial). 2. In the case of the k-vertex path graph, we show that it is always optimal for all players to use the same 1-bit function. 3. In the general case we show that all players should use monotone functions. 4. For certain trees it is better if not all players use the same function. Our techniques include the use of the reverse Bonami-Beckner inequality.

Review text

This note deals with so-called problem of non-interactive correlation distillation (NICD). In its most general form the problem involves \(k\) players who receive noisy copies of a uniformly random bit string of length \(n\). The players wish to agree on a single random bit but are not allowed to communicate. The problem is to understand the extent to which the players can successfully distill the correlations in their strings into a shared random bit. This problem is relevant for cryptographic information reconciliation, random beacons in cryptography and security, and coding theory. The paper contains the following new results: In the case of a \(k\)-leaf star graph they resolve the open question of whether the success probability must go to zero as \(k\to \infty\). The authors show that is indeed the case and provide matching upper and lower bounds on the asymptotically optimal rate(a slowly-decaying polynomial). In the case of the \(k\)-vertex path graph, they show that it is always optimal for all players to use the same 1-bit function. In the general case it is shown that all players should use monotone functions. They also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function.

Recommendations

• LATIN 2004: Theoretical Informatics
• On the (im)possibility of non-interactive correlation distillation
• On reverse hypercontractivity
• Tight bounds for communication-assisted agreement distillation
• On the correlation of increasing families

Cites work

• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Boolean functions with low average sensitivity depend on few coordinates
• Coin flipping from a cosmic source: On error correction of truly random bits
• Correlation inequalities on some partially ordered sets
• Derandomized graph products
• Discrete isoperimetric and Poincaré-type inequalities
• Every monotone graph property has a sharp threshold
• Families of Non-disjoint subsets
• Fourier analysis for probabilistic communication complexity
• Gibbs measures and phase transitions
• Global wellposedness of defocusing critical nonlinear Schrödinger equation in the radial case
• scientific article; zbMATH DE number 4106654 (Why is no real title available?)
• scientific article; zbMATH DE number 1966606 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Inequalities in Fourier analysis
• Influences of variables and threshold intervals under group symmetries
• Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
• Noise sensitivity of Boolean functions and applications to percolation
• Normal approximation - some recent advances
• On the power of unique 2-prover 1-round games
• Some optimal inapproximability results
• The importance of being biased
• The influence of variables in product spaces
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Uniform-distribution attribute noise learnability
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(29)

• Maximally stable Gaussian partitions with discrete applications
• A quantitative Arrow theorem
• On the round complexity of randomized Byzantine agreement
• Secure non-interactive simulation: feasibility and rate
• On reverse hypercontractivity
• On the (im)possibility of non-interactive correlation distillation
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• A quantitative Gobbard-Satterthwaite theorem without neutrality
• Quantum reverse hypercontractivity
• ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
• On percolation and \(\mathcal{NP}\)-hardness
• Geometric influences. II: Correlation inequalities and noise sensitivity
• Complete Minors in Graphs Without Sparse Cuts
• Probabilistic view of voting, paradoxes, and manipulation
• Dimension Reduction for Polynomials over Gaussian Space and Applications
• Coin flipping from a cosmic source: On error correction of truly random bits
• Hypercontractivity of Spherical Averages in Hamming Space
• Common Information, Noise Stability, and Their Extensions
• LATIN 2004: Theoretical Informatics
• Secure non-interactive simulation from arbitrary joint distributions
• On the \(\Phi \)-stability and related conjectures
• A phase transition in Arrow's theorem with three alternatives
• A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}
• A tight quantitative version of Arrow's impossibility theorem
• Density Frankl-Rödl on the sphere
• Talagrand-type correlation inequalities for supermodular and submodular functions on the hypercube
• Second-order converses via reverse hypercontractivity
• 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

This page was built for publication: Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality

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