ﻻ يوجد ملخص باللغة العربية
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 efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked, whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape, which can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
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
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 t
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
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