Entangled simultaneity versus classical interactivity in communication complexity

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Entangled simultaneity versus classical interactivity in communication complexity

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Entangled simultaneity versus classical interactivity in communication complexity

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016)

ISBN

978-1-4503-4132-5

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

877-884

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Cambridge

Datum konání akce

19. 6. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000455404200072