skip to main content

Title: 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 one-way communication complexity k in the standard model (i.e., without uncertainty, in other words, under the promise that f=g) has public-coin 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 public-coin uncertain communication was also shown. However, an important question that was left open is related to the power that public randomness brings to more » uncertain communication. Can Alice and Bob achieve efficient communication amid uncertainty without using public randomness? And how powerful are public-coin protocols in overcoming uncertainty? Motivated by these two questions: - We prove the first separation between private-coin uncertain communication and public-coin uncertain communication. Namely, we exhibit a function class for which the communication in the standard model and the public-coin uncertain communication are O(1) while the private-coin uncertain communication is a growing function of n (the length of the inputs). This lower bound (proved with respect to the uniform distribution) is in sharp contrast with the case of public-coin uncertain communication which was shown by the previous work to be within a constant factor from the certain communication. This lower bound also implies the first separation between public-coin uncertain communication and deterministic uncertain communication. Interestingly, we also show that if Alice and Bob imperfectly share a sequence of random bits (a setup weaker than public randomness), then achieving a constant blow-up in communication is still possible. - We improve the lower-bound of the previous work on public-coin uncertain communication. Namely, we exhibit a function class and a distribution (with mutual information I approx n) for which the one-way certain communication is k bits but the one-way public-coin uncertain communication is at least Omega(sqrt{k}*sqrt{I}) bits. Our proofs introduce new problems in the standard communication complexity model and prove lower bounds for these problems. Both the problems and the lower bound techniques may be of general interest. « less
Authors:
;
Award ID(s):
1650733
Publication Date:
NSF-PAR ID:
10078500
Journal Name:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
ISSN:
1868-8969
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 resource-efficiently. 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 non-constructive 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 well-studied 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 »are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975031.120« less
  2. The epsilon-approximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a real-valued 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 k-wise 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 epsilon-approximate 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/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise 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 »for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.« less
  3. 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 center-of-mass 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 single-particle $$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 »and with results from various general-purpose QCD-inspired Monte Carlo models. A hardening of the spectra at high $$p_{\mathrm{T}}$$ p T with increasing collision energy is observed, which is similar for all particle species under study. The transverse mass and $$x_{\mathrm{T}}\equiv 2p_{\mathrm{T}}/\sqrt{s}$$ x T ≡ 2 p T / s scaling properties of hadron production are also studied. As the collision energy increases from $$\sqrt{s}$$ s = 7–13 TeV, the yields of non- and single-strange hadrons normalized to the pion yields remain approximately constant as a function of $$\sqrt{s}$$ s , while ratios for multi-strange hadrons indicate enhancements. The $$p_\mathrm{{T}}$$ p T -differential cross sections of $$\pi ^{\pm }$$ π ± , $$\mathrm {K}^{\pm }$$ K ± and $$\mathrm {p}$$ p ( $$\overline{\mathrm{p}}$$ p ¯ ) are compared with next-to-leading order perturbative QCD calculations, which are found to overestimate the cross sections for $$\pi ^{\pm }$$ π ± and $$\mathrm{p}$$ p ( $$\overline{\mathrm{p}}$$ p ¯ ) at high $$p_\mathrm{{T}}$$ p T .« less
  4. 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, Ta-Shma, 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 .
  5. 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, Ta-Shma, 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.