Quantum Algorithms for Learning and Testing Juntas

L. G. Valiant, A Theory of the Learnable , Communications of the Association for Computing Machinery 27:11, pp. 1134–1142 (1984)

Original

1984

Earlier work this paper cites.

J. Kahn, G. Kalai, N. Linial, The influence of variables on boolean functions , Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 68–80 (1988)

1988

Earlier work this paper cites.

E. Kushilevitz, Y. Mansour, Learning Decision Trees using the Fourier Spectrum , SIAM Journal on Computing 22

1993

Earlier work this paper cites.

Y. Mansour. Learning Boolean functions via the Fourier transform , in “Theoretical Advances in Neural Computation and Learning,” Kluwer Academic Publishers, pp. 391-424 (1994)

1994

Earlier work this paper cites.

N. Bshouty, R. Cleve, R. Gavaldà, S. Kannan and C. Tamon. Oracles and queries that are sufficient for exact learning , J. Comput. Syst. Sci., Vol 52

1996

Earlier work this paper cites.

R. Rubinfeld and M. Sudan, Robust Characterizations of Polynomials with Applications to Program Testing , SIAM Journal on Computing, 25

1996

Earlier work this paper cites.

E. Bernstein, U. Vazirani, Quantum Complexity Theory , SIAM Journal of Computing, 26

1997

Earlier work this paper cites.

J. C. Jackson, An Efficient Membership-Query Algorithm for Learning 𝖣𝖭𝖥 \mathsf{DNF} with Respect to the Uniform Distribution , Journal of Computer and System Sciences 55

1997

Earlier work this paper cites.

O. Goldreich, S. Goldwasser, D. Ron, Property Testing and Its Connection to Learning and Approximation , Journal of the ACM, 45

1998

Earlier work this paper cites.

N. H. Bshouty, J. C. Jackson, Learning DNF over the Uniform Distribution Using a Quantum Example Oracle , SIAM J. Comput. Vol. 28

1999

Cited alongside, same era.

M. Nielsen and I. Chuang, Quantum Computation and Quantum Information , Cambridge University Press (2000)

2000

Cited alongside, same era.

E. Fischer, G. Kindler, D. Ron, S. Safra, A. Samorodnitsky, Testing Juntas , Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 103–112 (2002)

2002

Cited alongside, same era.

J. Arpe and R. Reischuk, Robust Inference of Relevant Attributes , Proceedings of the 14th International Conference on Algorithmic Learning Theory, pp. 99–113 (2003)

2003

Cited alongside, same era.

A. Blum, Learning a Function of r r Relevant Variables (Open Problem) , Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop, pp. 731–733 (2003)

E. Mossel, R. O’Donnell and R. A. Servedio, Learning Functions of k k Variables , Journal of Computer and System Sciences, Vol. 69

2004

Later among the works it cites.

R. A. Servedio, S. J. Gortler, Equivalences and Separations between Quantum and Classical Learnability , SIAM J. Comput. Vol. 33

2004

Later among the works it cites.

A. Atıcı, R. A. Servedio, Improved Bounds on Quantum Learning Algorithms , Quantum Information Processing, Vol. 4

2005

Later among the works it cites.

K. Iwama, A. Kawachi, R. Raymond and S. Yamashita, Robust Quantum Algorithms for Oracle Identification , arXiv:quant-ph/0411204 (2005)

2005

Later among the works it cites.

R. Lipton, E. Markakis, A. Mehta, N. Vishnoi, On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas , Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 112–119 (2005)