Quantum Lower Bound for the Collision Problem with Small Range

by Samuel Kutin

Theory of Computing, Volume 1(2), pp. 29-36, 2005

Bibliography with links to cited articles

[1] Scott Aaronson: Quantum lower bound for the collision problem. In Proc. of the 34th ACM STOC, pp. 635-642, 2002. [STOC:509907.509999, arXiv:quant-ph/0111102].
[2] Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595-605, 2004. Based on [10] and [1]. [JACM:1008735].
[3] Andris Ambainis: Quantum walk algorithm for element distinctness. In Proc. of the 45th IEEE FOCS, pp. 22-31, 2004. [FOCS:10.1109/FOCS.2004.54, arXiv:quant-ph/0311001].
[4] Andris Ambainis: Quantum lower bounds for collision and element distinctness with small range. Theory of Computing, 1(3), 2005. To appear. [ToC:v001/a003, arXiv:quant-ph/0305179].
[5] Bob Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. In Proc. of the 39th IEEE FOCS, pp. 352-361, 1998. [FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049].
[6] Gilles Brassard, Peter Høyer, and Alain Tapp: Quantum Cryptanalysis of Hash and Claw-Free Functions, volume 1380 of Lecture Notes in CS, pp. 163-169. Springer-Verlag, 1998. [LATIN:11bhjthw46dxl2qa, arXiv:quant-ph/9805082].
[7] Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. of the 28th ACM STOC, pp. 212-219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043].
[8] Noam Nisan and Márió Szegedy: On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. [STOC:129757].
[9] Ramamohan Paturi: On the degree of polynomials that approximate symmetric boolean functions. In Proc. of the 24th ACM STOC, pp. 468-474, 1992. [STOC:129758].
[10] Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. In Proc. of the 43th IEEE FOCS, pp. 513-519, 2002. [FOCS:10.1109/SFCS.2002.1181975, arXiv:quant-ph/0112086].
[11] Peter W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. [SICOMP:29317].

This file has been generated by bibtex2html 1.74