An official website of the United States government
We consider a scenario wherein two parties Alice and Bob are provided X1 and X2 – samples that are IID from a PMF P_X1X2. Alice and Bob can communicate to Charles over (noiseless) communication links of rate R1 and R2 respectively. Their goal is to enable Charles generate samples Y such that the triple (X1,X2,Y) has a PMF that is close, in total variation, to P_X1X2Y. In addition, the three parties may posses shared common randomness at rate C. We address the problem of characterizing the set of rate triples (R1, R2, C) for which the above goal can be accomplished. We provide a set of sufficient conditions, i.e., an achievable rate region for this three party setup. Our work also provides a complete characterization of a point-to-point setup wherein Bob is absent and Charles is provided with side-information.
more »
« less
Communication-rounds tradeoffs for common randomness and secret key generation
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1, X2, . . . and Y1, Y2, . . . with the pairs (X1, Y1), (X2, Y2), . . . being drawn independently from some known probability distribution μ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions μ = μr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b = b(r) for which CRG (respectively SKG) is feasible when (Xi, Yi) ~ μr,n,L with r + 1 rounds of communication, each consisting of O(log n) bits, but when restricted to r/2 − 2 rounds of interaction, the total communication must exceed Ω(n/ logb(n)) bits. Prior to our work no separations were known for r ≥ 2.
more »
« less
- Award ID(s):
- 1715187
- PAR ID:
- 10100407
- Date Published:
- Journal Name:
- Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
- Page Range / eLocation ID:
- 1861-1871
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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 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.more » « less
-
The cancellation problem asks whether A[X1,X2,…,Xn] ≅ B[Y1, Y2, . . . , Yn] implies A ≅ B. Hamann introduced the class of steadfast rings as the rings for which a version of the cancellation problem considered by Abhyankar, Eakin, and Heinzer holds. By work of Asanuma, Hamann, and Swan, steadfastness can be characterized in terms of p-seminormality, which is a variant of normality introduced by Swan. We prove that p-seminormality and steadfastness deform for reduced Noetherian local rings. We also prove that p-seminormality and steadfastness are stable under adjoining formal power series variables for reduced (not necessarily Noetherian) rings. Our methods also give new proofs of the facts that normality and weak normality deform, which are of independent interest.more » « less
-
Covert communication is achieved when a transmitter Alice can successfully transmit a message to a receiver Bob without being detected by an attentive and capable adversary Willie. Early results demonstrated the difficulty of the covert communications problem: with AWGN discrete-time channels between all parties, only O(sqrt(n)) bits can be sent in n channel uses. But it was soon recognized that uncertainty about the environment at Willie, for example, uncertainty in his own noise statistics, could allow for a positive rate: O(n) bits can be sent covertly in n channel uses. However, most covert communication results, including this promising positive rate result, have been obtained for a discrete-time communications channel. Here, we demonstrate that the assumption of a discrete-time channel is problematic when trying to exploit Willie's noise uncertainty. In particular, we demonstrate that if Alice transmits ω(sqrt(T)) bits in a length T interval to Bob on a continuous-time channel, then there exists a detector at Willie that can detect her transmission, as the probability of false alarm and missed detection PMD+PFA→0 as T→∞. In other words, the communication is not covert, unlike the case of a discrete-time channel.more » « less
-
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 .more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
