We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resourceefficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both nonconstructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two wellstudied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that theremore »
The Power of Shared Randomness in Uncertain Communication
In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function f and an input string x, and Bob is given a function g and an input string y. The pair (x,y) comes from a known distribution mu and f and g are guaranteed to be close under this distribution. Alice and Bob wish to compute g(x,y) with high probability. The lack of agreement between Alice and Bob on the function that is being computed captures the uncertainty in the context. The previous work showed that any problem with oneway communication complexity k in the standard model (i.e., without uncertainty, in other words, under the promise that f=g) has publiccoin communication at most O(k(1+I)) bits in the uncertain case, where I is the mutual information between x and y. Moreover, a lower bound of Omega(sqrt{I}) bits on the publiccoin uncertain communication was also shown.
However, an important question that was left open is related to the power that public randomness brings to more »
 Award ID(s):
 1650733
 Publication Date:
 NSFPAR ID:
 10078500
 Journal Name:
 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
 ISSN:
 18688969
 Sponsoring Org:
 National Science Foundation
More Like this


The epsilonapproximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a realvalued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly kwise indistinguishable, but are distinguishable by f with advantage 1  epsilon. Our contributions are:  We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilonapproximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3approximate degree of any (possibly unbalanced) readonce DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anticoncentration of the Binomial distribution.  We show that any pair of symmetric distributions on nbit strings that are perfectly kwise indistinguishable are also statistically Kwise indistinguishable with at most K^{3/2} * exp (Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantagemore »

Abstract The production of $$\pi ^{\pm }$$ π ± , $$\mathrm{K}^{\pm }$$ K ± , $$\mathrm{K}^{0}_{S}$$ K S 0 , $$\mathrm{K}^{*}(892)^{0}$$ K ∗ ( 892 ) 0 , $$\mathrm{p}$$ p , $$\phi (1020)$$ ϕ ( 1020 ) , $$\Lambda $$ Λ , $$\Xi ^{}$$ Ξ  , $$\Omega ^{}$$ Ω  , and their antiparticles was measured in inelastic proton–proton (pp) collisions at a centerofmass energy of $$\sqrt{s}$$ s = 13 TeV at midrapidity ( $$y<0.5$$  y  < 0.5 ) as a function of transverse momentum ( $$p_{\mathrm{T}}$$ p T ) using the ALICE detector at the CERN LHC. Furthermore, the singleparticle $$p_{\mathrm{T}}$$ p T distributions of $$\mathrm{K}^{0}_{S}$$ K S 0 , $$\Lambda $$ Λ , and $$\overline{\Lambda }$$ Λ ¯ in inelastic pp collisions at $$\sqrt{s} = 7$$ s = 7 TeV are reported here for the first time. The $$p_{\mathrm{T}}$$ p T distributions are studied at midrapidity within the transverse momentum range $$0\le p_{\mathrm{T}}\le 20$$ 0 ≤ p T ≤ 20 GeV/ c , depending on the particle species. The $$p_{\mathrm{T}}$$ p T spectra, integrated yields, and particle yield ratios are discussed as a function of collision energy and compared with measurements at lower $$\sqrt{s}$$ smore »

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set x ⊆ [ n ] and Bob ends up with a set y ⊆ [ n ], such that ( x , y ) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant β < 1, this requires Ω ( n ) communication even to get within statistical distance 1− β n of the target distribution. Previously, Ambainis, Schulman, TaShma, Vazirani, and Wigderson (FOCS 1998) proved that Ω (√ n ) communication is required to get within some constant statistical distance ɛ > 0 of the uniform distribution over all pairs of disjoint sets of size √ n .

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set x ⊆ [n] and Bob ends up with a set y ⊆ [n], such that (x, y) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant β < 1, this requires Ω(n) communication even to get within statistical distance 1 − β^n of the target distribution. Previously, Ambainis, Schulman, TaShma, Vazirani, and Wigderson (FOCS 1998) proved that Ω(√n) communication is required to get within some constant statistical distance ε > 0 of the uniform distribution over all pairs of disjoint sets of size √n.