×
Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis

Exponential separation of quantum and classical one-way communication complexity. (English) Zbl 1192.81052

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 128-137, electronic only (2004).

Cited in 17 Documents

MSC:

81P68 Quantum computation
68Qxx Theory of computing
68M12 Network protocols
Cite Review PDF
Full Text: DOI

References:

[1] S. Aaronson. Limitations of quantum advice and one-way communication. In Proceedings of the 19th IEEE Conference on Computational Complexity (CCC), 2004. to appear.]] 10.1109/CCC.2004.16
[2] A. Ambainis, L. J. Schulman, A. Ta-Shma, U. V. Vazirani, and A. Wigderson. The quantum communication complexity of sampling. SIAM J. on Computing, 32(6):1570-1585, 2003.]] 10.1137/S009753979935476 · Zbl 1041.68002
[3] L. Babai and P. G. Kimmel. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In Proceedings of the 12th IEEE Conference on Computational Complexity (CCC), pages 239-246, 1997.]] · Zbl 0995.68052
[4] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16), 2001.]]
[5] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), pages 63-68, 1998.]] 10.1145/276698.276713 · Zbl 1028.68056
[6] T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 1991.]] · Zbl 0762.94001
[7] P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357-368, 1981.]] · Zbl 0498.05048
[8] M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. on Computing, 26(5):255-265, 1990.]] · Zbl 0695.94021
[9] I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via quantum argument. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pages 106-115, 2003.]] 10.1145/780542.780560 · Zbl 1192.81082
[10] H. Klauck. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pages 644-651, 2000.]] 10.1145/335305.335396 · Zbl 1296.68058
[11] I. Kremer. Quantum Communication. Master’s Thesis, The Hebrew University of Jerusalem, 1995.]]
[12] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.]] · Zbl 0869.68048
[13] I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39:67-71, 1991.]] 10.1016/0020-0190(91)90157-D · Zbl 0735.68034
[14] I. Newman and M. Szegedy. Public vs. private coin flips in one round communication games. In Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pages 561-570, 1996.]] 10.1145/237814.238004 · Zbl 0936.68050
[15] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.]] · Zbl 1049.81015
[16] R. Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), pages 358-367, 1999.]] 10.1145/301250.301343 · Zbl 1345.68134
[17] P. Sen and S. Venkatesh. Lower bounds in the quantum cell probe model. In Proceedings of the 28th ICALP, volume 2076, pages 358-369, 2001.]] · Zbl 0986.68022
[18] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. on Computing, 26(5):1484-1509, 1997.]] 10.1137/S0097539795293172 · Zbl 1005.11065
[19] A. C. -C. Yao. Some complexity questions related to distributive computing. In Proceedings of the 11th ACM Symposium on Theory of Computing (STOC), pages 209-213, 1979.]] 10.1145/800135.804414
[20] A. C. -C. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 420-428, 1983.]]
[21] A. C. -C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 352-361, Los Alamitos, CA, 1993.]]
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.