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 »
Authors:
;
Award ID(s):
Publication Date:
NSF-PAR ID:
10078500
Journal Name:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
ISSN:
1868-8969
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 »