Entangled simultaneity versus classical interactivity in communication complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00463615" target="_blank" >RIV/67985840:_____/16:00463615 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/2897518.2897545" target="_blank" >http://dx.doi.org/10.1145/2897518.2897545</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2897518.2897545" target="_blank" >10.1145/2897518.2897545</a>
Alternative languages
Result language
angličtina
Original language name
Entangled simultaneity versus classical interactivity in communication complexity
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)
ISBN
978-1-4503-4132-5
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
877-884
Publisher name
ACM
Place of publication
New York
Event location
Cambridge
Event date
Jun 19, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000455404200072