In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a problem that we introduce and prove the first lower bound for, but it is a generalization of a well-known problem called the Boolean Hidden Matching, that was used by Gavinsky et al. to prove separations between quantum communication complexity and one-way randomized communication complexity. The hardness of the BHH problem is inherently one-way: it is easy to solve using logarithmic two-way communication, but requires √ n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, for approximately counting the number of cycles in a 2-regular graph, and for other problems. For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching EA on a set of n nodes, and Bob gets a perfect matching EB on the same set of nodes. The union EA ∪ EB is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o ( √ n) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1.999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is “natively ” one-way: With 4 rounds of communication, it is easy to distinguish these two cases. 1
In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a problem that we introduce and prove the first lower bound for, but it is a generalization of a well-known problem called the Boolean Hidden Matching, that was used by Gavinsky et al. to prove separations between quantum communication complexity and one-way randomized communication complexity. The hardness of the BHH problem is inherently one-way: it is easy to solve using logarithmic two-way communication, but requires √ n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, for approximately counting the number of cycles in a 2-regular graph, and for other problems. For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching EA on a set of n nodes, and Bob gets a perfect matching EB on the same set of nodes. The union EA ∪ EB is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o ( √ n) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1.999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is “natively ” one-way: With 4 rounds of communication, it is easy to distinguish these two cases. 1
In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BHH). BHH is a generalization of the well-known Boolean Hidden Matching problem, which was used by Gavinsky et al. to prove an exponential separation between quantum communication complexity and one-way randomized communication complexity. We are the first to introduce BHH, and to prove a lower bound for it. The hardness of the BHH problem is inherently one-way: it is easy to solve BHH using logarithmic two-way communication, but it requires √n communication if Alice is only allowed to send messages to Bob, and not vice-versa. This one-wayness allows us to prove lower bounds, via reductions, for streaming problems and related communication problems whose hardness is also inherently one-way. By designing reductions from BHH, we prove lower bounds for the streaming complexity of approximating the sorting by reversal distance, of approximately counting the number of cycles in a 2-regular graph, and of other problems. For example, here is one lower bound that we prove, for a cycle-counting problem: Alice gets a perfect matching EA on a set of n nodes, and Bob gets a perfect matching EB on the same set of nodes. The union EA ∪ EB is a collection of cycles, and the goal is to approximate the number of cycles in this collection. We prove that if Alice is allowed to send o(√n) bits to Bob (and Bob is not allowed to send anything to Alice), then the number of cycles cannot be approximated to within a factor of 1.999, even using a randomized protocol. We prove that it is not even possible to distinguish the case where all cycles are of length 4, from the case where all cycles are of length 8. This lower bound is “natively” one-way: With 4 rounds of communication, it is easy to distinguish these two cases.
Abstract. We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ {0,1} n, and Bob gets a perfect matching M on the n coordinates. Bob’s goal is to output a tuple 〈i, j, b 〉 such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(logn), yet any randomized one-way protocol with bounded error must use Ω ( √ n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(logn) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω ( 3 √ nlog n) bits of communication.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩ such that the edge (i,j) belongs to the matching M and b=xi⊕xj. We prove that the quantum one-way communication complexity of HMn is O(logn), yet any randomized one-way protocol with bounded error must use Ω(n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(logn) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(3nlogn) bits of communication.
We study the one-way communication complexity of the f-Boolean Hidden Partition problem. Here, Alice is given an n-bit string and Bob is given Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of f on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where f is the parity function.
We establish classical and quantum communication bounds for f-Boolean Hidden Partition in terms of the sign degree d of f, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1 and quantum protocols when d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every f of sign degree d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions f admitting polynomial quantum advantage as those for which d≥2, with a new infinite family of exponential separations given by the case d=2.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function f. Efficient communication protocols are presented depending on the sign-degree of f. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to 2, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions f of sign-degree greater than or equal to 2, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function f whose pure high degree is greater than or equal to 2. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function f whose pure high degree is greater than or equal to 3. These results give a large family of new exponential classical-quantum communication separations.