ﻻ يوجد ملخص باللغة العربية
We study the communication complexity of computing functions $F:{0,1}^ntimes {0,1}^n rightarrow {0,1}$ in the memoryless communication model. Here, Alice is given $xin {0,1}^n$, Bob is given $yin {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. (ITCS13), space bounded communication complexity by Brody et al. (ITCS13) and the overlay communication complexity by Papakonstantinou et al. (CCC14). 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 $c log n$? Note that $cgeq 2+varepsilon$ would imply a $Omega(n^{2+varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nev{c}iporuk in 1966.
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously stu
This work addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research, which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common
In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existed a function with an efficient quantum one-way protocol, but still no
The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to gi