nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Equality, Revisited

verfasst von : Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 \(\varOmega {\left( \sqrt{n}\right) }\) 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.

Some of our results highlight that NE is easier than EQ in the presence of classical proofs, whereas the problems have (roughly) the same complexity when a quantum proof is present.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Metric Dimension of Bounded Width Graphs

Nächstes Kapitel Bounding the Clique-Width of H-free Chordal Graphs

The communication complexity of EQ becomes n in the most of deterministic models, but those results are usually trivial and we do not consider the deterministic setup in this work (except for one special case where a “semi-deterministic” protocol has complexity \(O{\left( \sqrt{n}\right) }\) – that situation will be analysed in one of our lower bound proofs).

Note that Merlin’s message is only seen by the referee, and not by Alice and Bob. Letting the players receive messages from Merlin prior to sending their own messages would contradict the “simultaneous flavour” of the SMP model. Practically, that would make NE trivial; while the case of EQ is less obvious, we believe that the techniques developed in this work would be useful there as well.

The best lower bound that we were able to prove using combinations of known techniques is \(\tilde{\varOmega }(n^{1/3})\).

Aaronson, S.: Limitations of quantum advice and one-way communication. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 320–332 (2004)

Aaronson, S.: QMA/qpoly \(\subseteq \) pspace/poly: de-merlinizing quantum protocols. In: Proceedings of 21st IEEE Conference on Computational Complexity (2006)

Ambainis, A.: Communication complexity in a 3-computer model. Algorithmica 16(3), 298–301 (1996)MathSciNetCrossRefMATH

Babai, L., Kimmel, P.: Randomized simultaneous messages: solution of a problem of yao in communication complexity. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p. 239 (1997)

Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum Fingerprinting. Phys. Rev. Lett. 87(16), 167902 (2001)CrossRef

Dasgupta, S., Gupta, A.: An elementary proof of a theorem of johnson and lindenstrauss. Random Struct. Algorithms 22(1), 60–65 (2003)MathSciNetCrossRefMATH

Fuchs, C.A., van de Graaf, J.: Cryptographic distinguishability measures for quantum-mechanical states. IEEE Trans. Inf. Theory 45(4), 1216–1227 (1999)MathSciNetCrossRefMATH

Gavinsky, D., Regev, O., de Wolf, R.: Simultaneous communication protocols with quantum and classical messages. Chicago J. Theor. Comput. Sci. 7 (2008)

Hiai, F., Ohya, M., Tsukada, M.: Sufficiency, KMS condition and relative entropy in von neumann algebras. Pacific J. Math. 96, 99–109 (1981)MathSciNetCrossRefMATH

10.

Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum communication and the complexity of set disjointness. In: Proceedings of 33rd ACM STOC, pp. 124–133 (2001)

11.

Klauck, H., Podder, S.: Two results about quantum messages. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 445–456. Springer, Heidelberg (2014)

12.

Kobayashi, H., Matsumoto, K., Yamakami, T.: Quantum merlin-arthur proof systems: are multiple merlins more helpful to arthur? In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 189–198. Springer, Heidelberg (2003) CrossRef

13.

Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)CrossRefMATH

14.

Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett. 39(2), 67–71 (1991)MathSciNetCrossRefMATH

15.

Newman, I., Szegedy,v: Public vs. private coin flips in one round communication games. In: Proceedings of the 28th Symposium on Theory of Computing, pp. 561–570 (1996)

16.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2000)MATH

17.

de Wolf, R.: Quantum communication and complexity. Theor. Comput. Sci. 287(1), 337–353 (2002)MathSciNetCrossRefMATH

18.

Yao, A.C-C.: Some complexity questions related to distributed computing. In: Proceedings of the 11th Symposium on Theory of Computing, pp. 209–213 (1979)

Titel: Equality, Revisited
verfasst von: Ralph Bottesch
Dmitry Gavinsky
Hartmut Klauck
Verlag: Springer Berlin Heidelberg
Buch: Mathematical Foundations of Computer Science 2015
Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-48054-0_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"