In this chapter we consider several, more advanced, topics related to the two-party communication model. Direct Sum The direct-sum problem is the following: Alice gets two inputs x f ∈ X f and x g ∈ X g . Bob gets two inputs y f ∈ Y f and y g ∈ Y g . They wish to compute both f ( x f , y f ) and g ( x g , y g ). The obvious solution would be for Alice and Bob to use the best protocol for f to compute the first value, f ( x f , y f ) and the best protocol for g to compute the second value, g ( x g , y g ). We stress that the two subproblems are totally independent. Thus one would tend to conjecture that nothing better than the obvious solution can be done: Alice and Bob cannot “save” any communication over the obvious protocol. As we shall see, in some cases and for some measures of complexity, this intuition is wrong. Denote by D ( f , g ) the (deterministic) communication complexity of this computation. Similarly, we define all other complexity measures such as R ( f , g ), N ( f , g ), and so forth. We also use the notation D ( f ℓ ) as the (deterministic) communication complexity of computing f and ℓ instances; that is, computing f ( x 1 , y 1 ), f ( x 2 , y 2 ), …, f ( x ℓ , y ℓ Open Problem 4.1: Can D ( f , g ) be smaller than D ( f ) + D ( g )? How much smaller can it be? How much smaller can D ( f ℓ ) be compared to ℓ · D ( f )? In some cases we are not interested in computing both f and g but rather some function of the two.
In this chapter we consider several, more advanced, topics related to the two-party communication model. Direct Sum The direct-sum problem is the following: Alice gets two inputs x f ∈ X f and x g ∈ X g . Bob gets two inputs y f ∈ Y f and y g ∈ Y g . They wish to compute both f ( x f , y f ) and g ( x g , y g ). The obvious solution would be for Alice and Bob to use the best protocol for f to compute the first value, f ( x f , y f ) and the best protocol for g to compute the second value, g ( x g , y g ). We stress that the two subproblems are totally independent. Thus one would tend to conjecture that nothing better than the obvious solution can be done: Alice and Bob cannot “save” any communication over the obvious protocol. As we shall see, in some cases and for some measures of complexity, this intuition is wrong. Denote by D ( f , g ) the (deterministic) communication complexity of this computation. Similarly, we define all other complexity measures such as R ( f , g ), N ( f , g ), and so forth. We also use the notation D ( f ℓ ) as the (deterministic) communication complexity of computing f and ℓ instances; that is, computing f ( x 1 , y 1 ), f ( x 2 , y 2 ), …, f ( x ℓ , y ℓ Open Problem 4.1: Can D ( f , g ) be smaller than D ( f ) + D ( g )? How much smaller can it be? How much smaller can D ( f ℓ ) be compared to ℓ · D ( f )? In some cases we are not interested in computing both f and g but rather some function of the two.
Direct-sum questions in (two-party) communication complexity ask whether two parties, Alice and Bob, can compute the value of a function f on l inputs (x_1,y_1),...,(x_l,y_l) more efficiently than by applying the best protocol for f, independently on each input (x_i,y_i). In spite of significant efforts to understand these questions (under various communication-complexity measures), the general question is still far from being well understood. In this paper, we offer a multiparty view of these questions: The direct-sum setting is just a two-player system with Alice having inputs x_1,...,x_l, Bob having inputs y_1,...,y_l and the desired output is f(x_1,y_1),...,f(x_l,y_l). The naive solution of solving the l problems independently, is modeled by a network with l (disconnected) pairs of players Alice i and Bob i, with inputs x_i,y_i respectively, and communication only within each pair. Then, we consider an intermediate ("star") model, where there is one Alice having l inputs x_1,...,x_l and l players Bob_1,...,Bob_l holding y_1,...,y_l, respectively (in fact, we consider few variants of this intermediate model, depending on whether communication between each Bob i and Alice is point-to-point or whether we allow broadcast). Our goal is to get a better understanding of the relation between the two extreme models (i.e., of the two-party direct-sum question). If, for instance, Alice and Bob can do better (for some complexity measure) than solving the l problems independently, we wish to understand what intermediate model already allows to do so (hereby understanding the "source" of such savings). If, on the other hand, we wish to prove that there is no better solution than solving the l problems independently, then our approach gives a way of breaking the task of proving such a statement into few (hopefully, easier) steps. We present several results of both types. Namely, for certain complexity measures, communication problems f and certain pairs of models, we can show gaps between the complexity of solving f on l instances in the two models in question; while, for certain other complexity measures and pairs of models, we can show that such gaps do not exist (for any communication problem f). For example, we prove that if only point-to-point communication is allowed in the intermediate "star" model, then significant savings are impossible in the public-coin randomized setting. On the other hand, in the private-coin randomized setting, if Alice is allowed to broadcast messages to all Bobs in the "star" network, then some savings are possible. While this approach does not lead yet to new results on the original two-party direct-sum question, we believe that our work gives new insights on the already-known direct-sum results, and may potentially lead to more such results in the future.
In communication complexity the input of a function f:X×Y→Z is distributed between two players Alice and Bob. If Alice knows only x∈X and Bob only y∈Y, how much information must Alice and Bob share to be able to elicit the value of f(x,y)? Do we need ℓ more resources to solve ℓ instances of a problem? This question is the direct sum question and has been studied in many computational models. In this paper we focus on the case of 2-party deterministic communication complexity and give a counterexample to the direct sum conjecture in its strongest form. To do so we exhibit a family of functions for which the complexity of solving ℓ instances is less than (1−ε)ℓ times the complexity of solving one instance for some small enough ε>0. We use a customised method in the analysis of our family of total functions, showing that one can force the alternation of rounds between players. This idea allows us to exploit the integrality of the complexity measure to create an increasing gap between the complexity of solving the instances independently with that of solving them together.
Consider the following Simultaneous Message Passing (SMP) model for computing a relation f subset of X x Y x Z. In this model Alice, on input x in X and Bob, on input y in Y, send one message each to a third party Referee who then outputs a z in Z such that (x,y,z) in f. We first show optimal 'Direct sum' results for all relations f in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of f, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier Direct sum result, shown by Chakrabarti, Shi, Wirth and Yao, 2001, for the Equality function (and a class of other so-called robust functions), in the classical smp model with no shared resources between any parties. Furthermore we investigate the gap between the smp model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.
Consider the following simultaneous message passing (SMP) model for computing a relation f sube X times Y times Z. In this model Alice, on input x isin X and Bob, on input y isin Y, send one message each to a third party Referee who then outputs a z isin Z such that (x, y, z) isin f. We first show optimal direct sum results for all relations / in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of /, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
We study the communication complexity of computing functions F:{0,1}n×{0,1}n→{0,1} in the memoryless communication model. Here, Alice is given x∈{0,1}n, Bob is given y∈{0,1}n and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least clogn? Note that c≥2+ε would imply a Ω(n2+ε) lower bound for general formula size, improving upon the best lower bound by Nečiporuk in 1966.