Equality, Revisited
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00447630" target="_blank" >RIV/67985840:_____/15:00447630 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-662-48054-0_11" target="_blank" >http://dx.doi.org/10.1007/978-3-662-48054-0_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-48054-0_11" target="_blank" >10.1007/978-3-662-48054-0_11</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Equality, Revisited
Popis výsledku v původním jazyce
We develop a new lower bound method for analysing the complexity of the Equality function (EQ) in the Simultaneous Message Passing (SMP) model of communication complexity. The new technique gives tight lower bounds of ?(n) for both EQ and its negation NEin the non-deterministic version of quantum-classical SMP, where Merlin is also quantum ? this is the strongest known version of SMP where the complexity of both EQ and NE remain high (previously known techniques seem to be insufficient for this). Besides, our analysis provides to a unified view of the communication complexity of EQ and NE, allowing to obtain tight characterisation in all previously studied and a few newly introduced versions of SMP, including all possible combination of either quantumor randomised Alice, Bob and Merlin in the non-deterministic case.
Název v anglickém jazyce
Equality, Revisited
Popis výsledku anglicky
We develop a new lower bound method for analysing the complexity of the Equality function (EQ) in the Simultaneous Message Passing (SMP) model of communication complexity. The new technique gives tight lower bounds of ?(n) for both EQ and its negation NEin the non-deterministic version of quantum-classical SMP, where Merlin is also quantum ? this is the strongest known version of SMP where the complexity of both EQ and NE remain high (previously known techniques seem to be insufficient for this). Besides, our analysis provides to a unified view of the communication complexity of EQ and NE, allowing to obtain tight characterisation in all previously studied and a few newly introduced versions of SMP, including all possible combination of either quantumor randomised Alice, Bob and Merlin in the non-deterministic case.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
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
Ostatní
Rok uplatnění
2015
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Mathematical Foundations of Computer Science 2015
ISBN
978-3-662-48053-3
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
127-138
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Milan
Datum konání akce
28. 8. 2015
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—