Equality, Revisited
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Equality, Revisited
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
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
2015
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
Mathematical Foundations of Computer Science 2015
ISBN
978-3-662-48053-3
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
127-138
Publisher name
Springer
Place of publication
Berlin
Event location
Milan
Event date
Aug 28, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—