We show an Ω(√n/T) lower bound for the space required by any unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak (2009) and rigorously establishes that bidirectional streams are exponentially more efficient in space usage as compared with unidirectional ones. We obtain the lower bound by analyzing the information that is necessarily revealed by the players about their respective inputs in a two-party communication protocol for a variant of the index function, namely augmented index. We show that in any communication protocol that computes this function correctly with constant error on the uniform distribution (a “hard” distribution), either Alice reveals Ω(n) information about her n-bit input, or Bob reveals Ω(1) information about his (logn)-bit input, even when the inputs are drawn from an “easy” distribution, the uniform distribution over inputs that evaluate to 0. The information cost tradeoff is obtained by a novel application of the conceptually simple and familiar ideas, such as average encoding and the cut-and-paste property, of randomized protocols. Motivated by recent examples of exponential savings in space by streaming quantum algorithms, we also study quantum protocols for augmented index. Defining an appropriate notion of information cost for quantum protocols involves a delicate balancing act between its applicability and the ease with which we can analyze it. We define a notion of quantum information cost, which reflects some of the nonintuitive properties of quantum information. We show that in quantum protocols that compute the augmented index function correctly with constant error on the uniform distribution, either Alice reveals Ω(n/t) information about her n-bit input, or Bob reveals Ω(1/t) information about his (log n)-bit input, where t is the number of messages in the protocol, even when the inputs are drawn from the abovementioned easy distribution. While this tradeoff demonstrates the strength of our proof techniques, it does not lead to a space lower bound for checking parentheses. We leave such an implication for quantum streaming algorithms as an intriguing open question.
We show an Ω(√n/T) lower bound for the space required by any unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak (2009) and rigorously establishes that bidirectional streams are exponentially more efficient in space usage as compared with unidirectional ones. We obtain the lower bound by analyzing the information that is necessarily revealed by the players about their respective inputs in a two-party communication protocol for a variant of the index function, namely augmented index. We show that in any communication protocol that computes this function correctly with constant error on the uniform distribution (a “hard” distribution), either Alice reveals Ω(n) information about her n-bit input, or Bob reveals Ω(1) information about his (logn)-bit input, even when the inputs are drawn from an “easy” distribution, the uniform distribution over inputs that evaluate to 0. The information cost tradeoff is obtained by a novel application of the conceptually simple and familiar ideas, such as average encoding and the cut-and-paste property, of randomized protocols. Motivated by recent examples of exponential savings in space by streaming quantum algorithms, we also study quantum protocols for augmented index. Defining an appropriate notion of information cost for quantum protocols involves a delicate balancing act between its applicability and the ease with which we can analyze it. We define a notion of quantum information cost, which reflects some of the nonintuitive properties of quantum information. We show that in quantum protocols that compute the augmented index function correctly with constant error on the uniform distribution, either Alice reveals Ω(n/t) information about her n-bit input, or Bob reveals Ω(1/t) information about his (log n)-bit input, where t is the number of messages in the protocol, even when the inputs are drawn from the abovementioned easy distribution. While this tradeoff demonstrates the strength of our proof techniques, it does not lead to a space lower bound for checking parentheses. We leave such an implication for quantum streaming algorithms as an intriguing open question.
We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with potential for broader applicability, and use them to establish a lower bound on the quantum information complexity for the Augmented Index function on an easy distribution. This approach allows us to handle superpositions rather than distributions over inputs, the main technical challenge faced previously. By providing a quantum generalization of the argument of Jain and Nayak [IEEE TIT'14], we leverage this to obtain a lower bound on the space complexity of multi-pass, unidirectional quantum streaming algorithms for the DYCK(2) language.
Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.
We derive lower bounds for tradeoffs between the communication C and space S for communicating circuits. The first such bound applies to quantum circuits. If for any function f with image Z the multicolor discrepancy of the communication matrix of f is 1/2^d, then any bounded error quantum protocol with space S, in which Alice receives some l inputs, Bob r inputs, and they compute f(x_i,y_j) for the lr pairs of inputs (x_i,y_j) needs communication C=Ω(lrd \log |Z|/S). In particular, n\times n-matrix multiplication over a finite field F requires C=Θ(n^3\log^2 |F|/S). We then turn to randomized bounded error protocols, and derive the bound C=Ω(n^3/S^2) for Boolean matrix multiplication, utilizing a new direct product result for the one-sided rectangle lower bound on randomized communication complexity. This implies a separation between quantum and randomized protocols.
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 define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.
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.