Quantum property testing for bounded-degree graphs

M. Pinsker. On the complexity of a concentrator. In Proceedings of the 7th International Teletraffic Conference, pages 318/1-318/4. 1973

1973

Earlier work this paper cites.

N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms 7 (4):567-583, 1986

1986

Earlier work this paper cites.

N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms 3 (3):289-304, 1992

1992

Earlier work this paper cites.

R. Paturi. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In STOC, pages 468-474. 1992

1992

Earlier work this paper cites.

R. Motwani and P. Raghavan. Randomized Algorithms, 1995. Cambridge University Press

1995

Earlier work this paper cites.

D. R. Simon. On the power of quantum computation. SIAM J. on Computing 26 (5):1474-1483, 1997

1997

Earlier work this paper cites.

O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. of the ACM 45 (4):653-750, 1998

1998

Earlier work this paper cites.

O. Goldreich and D. Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica 19 (3):335-373, 1999

1999

Earlier work this paper cites.

O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs, 2000. ECCC report TR00-020

2000

Earlier work this paper cites.

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. of the ACM 48 (4):778-797, 2001

2001

Earlier work this paper cites.

O. Goldreich. Randomized Methods in Computation, 2001. Lecture notes available at http://www.wisdom.weizmann.ac.il/ ∼ \sim oded/rnd.html, Lecture 2

2001

Earlier work this paper cites.

S. Aaronson. Quantum lower bound for the collision problem. In STOC, pages 635-642. 2002

2002

Earlier work this paper cites.

A. Ambainis. Quantum lower bounds by quantum arguments. J. of Computer and System Sciences 64 (4):750-767, 2002

2002

Cited alongside, same era.

O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica 32 (2):302-343, 2002

2002

Cited alongside, same era.

Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. In FOCS, pages 513-519. 2002

2002

Cited alongside, same era.

M. Szegedy. Quantum speed-up of Markov chain based algorithms. In FOCS, pages 32-41. 2004

2004

Cited alongside, same era.

H. Buhrman, C. Durr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha, and R. de Wolf. Quantum algorithms for element distinctness. SIAM J. on Computing 34 (6):1324-1330, 2005

2005

Cited alongside, same era.

F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. SIAM J. on Computing 37 (2):413-424, 2007

2007

Later among the works it cites.

F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. In STOC, pages 575-584. 2007

2007

Later among the works it cites.

H. Buhrman, L. Fortnow, I. Newman, and H. Rohrig. Quantum property testing. SIAM J. on Computing 37 (5):1387-1400, 2008

2008

Later among the works it cites.

Y. Inui and F. L. Gall. Quantum property testing of group solvability. In LATIN, pages 772-783. 2008

2008

Later among the works it cites.

M. Santha. Quantum walk based search algorithms. In Theory and Applications of Models of Computation, pages 31-46. 2008

2008

Later among the works it cites.