Equality, Revisited

0447630 - MÚ 2016 RIV DE eng C - Conference Paper (international conference)
Bottesch, R. - Gavinsky, Dmitry - Klauck, H.
Equality, Revisited.
Mathematical Foundations of Computer Science 2015. Berlin: Springer, 2015 - (Italiano, G.; Pighizzini, G.; Sannella, D.), s. 127-138. Lecture Notes in Computer Science, vol. 9235. ISBN 978-3-662-48053-3.
[International Symposium of Mathematical Foundations of Computer Science 2015, MFCS 2015. Milan (IT), 28.08.2015-28.08.2015]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : equality * complexity * algorithm analysis
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007/978-3-662-48054-0_11

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 NE in 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 quantum or randomised Alice, Bob and Merlin in the non-deterministic case.
Permanent Link: http://hdl.handle.net/11104/0249435