Bibliography: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science

All Quantum Adversary Methods are Equivalent

Theory of Computing, Volume 2(1), pp. 1-18, 2006

Bibliography with links to cited articles

[1]	S. Aaronson and Y. Shi: Quantum lower bounds for the collision and the element distinctness problem. Journal of the ACM, 51(4):595-605, 2004. [JACM:1008731.1008735, arXiv:quant-ph/0111102].
[2]	A. Ambainis: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002. Earlier version in STOC '00. [JCSS:10.1006/jcss.2002.1826, STOC:335305.335394, arXiv:quant-ph/0002066].
[3]	A. Ambainis: Polynomial degree vs. quantum query complexity. In Proc. of 44th IEEE FOCS, pp. 230-239, 2003. [FOCS:10.1109/SFCS.2003.1238197, arXiv:quant-ph/0305028].
[4]	A. Ambainis: Quantum walk algorithm for element distinctness. In Proc. of 45th IEEE FOCS, pp. 22-31, 2004. [arXiv:quant-ph/0311001].
[5]	A. Ambainis: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1:37-46, 2005. [ToC:v001/a003, arXiv:quant-ph/0305179].
[6]	H. Barnum and M. Saks: A lower bound on the quantum query complexity of read-once functions. Journal of Computer and System Sciences, 69(2):244-258, 2004. [JCSS:10.1016/j.jcss.2004.02.002, arXiv:quant-ph/0201007].
[7]	H. Barnum, M. Saks, and M. Szegedy: Quantum decision trees and semidefinite programming. In Proc. of 18th IEEE Complexity, pp. 179-193, 2003. [CCC:10.1109/CCC.2003.1214419].
[8]	R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf: Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. Earlier version in FOCS '98. [JACM:502090.502097, FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049].
[9]	H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510-1523, 1997. [SICOMP:30093, arXiv:quant-ph/9701001].
[10]	H. Buhrman and R. Spalek: Quantum verification of matrix products. In Proc. of 17th ACM-SIAM SODA, pp. 880-889, 2006. [SODA:1109557.1109654, arXiv:quant-ph/0409035].
[11]	H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21-43, 2002. [TCS:10.1016/S0304-3975(01)00144-X]. [ .ps ]
[12]	L. K. Grover: A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pp. 212-219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043].
[13]	P. Høyer, M. Mosca, and R. de Wolf: Quantum search on bounded-error inputs. In Proc. of 30th ICALP, pp. 291-299, 2003. LNCS 2719. [ICALP:214dhep41d6vk3d2, arXiv:quant-ph/0304052].
[14]	P. Høyer, J. Neerbek, and Y. Shi: Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34(4):429-448, 2002. Special issue on Quantum Computation and Cryptography. [Algorithmica:25gl9elr5rxr3q6a, arXiv:quant-ph/0102078].
[15]	P. Høyer and R. Spalek: Lower bounds on quantum query complexity. EATCS Bulletin, 87:78-103, October, 2005. [arXiv:quant-ph/0509153].
[16]	S. Laplante, T. Lee, and M. Szegedy: The quantum adversary method and formula size lower bounds. In Proc. of 20th IEEE Complexity, pp. 76-90, 2005. [CCC:10.1109/CCC.2005.29, arXiv:quant-ph/0501057].
[17]	S. Laplante and F. Magniez: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In Proc. of 19th IEEE Complexity, pp. 294-304, 2004. [CCC:10.1109/CCC.2004.1313852, arXiv:quant-ph/0311189].
[18]	M. Li and P. M. B. Vitányi: An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin, second edition, 1997.
[19]	L. Lovász: Semidefinite programs and combinatorial optimization. http://research.microsoft.com/users/lovasz/semidef.ps, 2000. [ .ps ]
[20]	F. Magniez, M. Santha, and M. Szegedy: Quantum algorithms for the triangle problem. In Proc. of 16th ACM-SIAM SODA, pp. 1109-1117, 2005. [SODA:1070432.1070591, arXiv:quant-ph/0310134].
[21]	R. Mathias: The spectral norm of a nonnegative matrix. Linear Algebra and its Applications, 139:269-284, 1990. [laa:10.1016/0024-3795(90)90403-Y]. [ .ps.gz ]
[22]	M. A. Nielsen and I. L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.
[23]	M. Saks and A. Wigderson: Probabilistic Boolean decision trees and the complexity of evaluating games trees. In Proc. of 27th IEEE FOCS, pp. 29-38, 1986. [ .ps \| .pdf ]
[24]	M. Santha: On the Monte Carlo decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75-87, 1995. [ .ps.gz ]
[25]	M. Snir: Lower bounds on probabilistic decision trees. Theoretical Computer Science, 38:69-82, 1985. [TCS:10.1016/0304-3975(85)90210-5].
[26]	M. Szegedy: On the quantum query complexity of detecting triangles in graphs. quant-ph/0310107, 2003. [arXiv:quant-ph/0310107].
[27]	S. Zhang: On the power of Ambainis's lower bounds. Theoretical Computer Science, 339(2-3):241-256, 2005. Earlier version in ICALP'04. [TCS:10.1016/j.tcs.2005.01.019, ICALP:gm2ff6wpc0q39v3x, arXiv:quant-ph/0311060].

This file has been generated by bibtex2html 1.74