Fetching the paper…
Reading the bibliography…
In this paper, we study the following variant of the junta learning problem.
Representation theory of finite groups and associative algebras
C. W. Curtis and I. Reiner · 1962
Earlier work this paper cites.
Orthogonal polynomials
G. Szegő · 1975
Earlier work this paper cites.
Linear Representations of Finite Groups
J.-P. Serre · 1977
Earlier work this paper cites.
Queries and concept learning
D. Angluin · 1988
Earlier work this paper cites.
Combinatorial group testing and its applications
D. Z. Du and F. Hwang · 1993
Earlier work this paper cites.
A pretty good measurement for distinguishing quantum states
P. Hausladen and W. K. Wootters · 1994
Earlier work this paper cites.
Oracles and queries that are sufficient for exact learning
N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and C. Tamon · 1996
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Learning DNF over the uniform distribution using a quantum example oracle
N. H. Bshouty and J. C. Jackson · 1998
Earlier work this paper cites.
Quantum oracle interrogation: Getting all information for almost half the price
W. van Dam · 1998
Earlier work this paper cites.
Grover’s quantum searching algorithm is optimal
C. Zalka · 1999
Earlier work this paper cites.
Survey of binary Krawtchouk polynomials
I. Krasikov and S. Litsyn · 2001
Earlier work this paper cites.
The symmetric group: representations, combinatorial algorithms, and symmetric functions
B. E. Sagan · 2001
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2002
Earlier work this paper cites.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
Exponential algorithmic speedup by a quantum walk
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman · 2003
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Cited alongside, same era.
Quantum identification of boolean oracles
A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. H. Putra, and S. Yamashita · 2004
Cited alongside, same era.
Convex optimization
S. Boyd and L. Vandenberghe · 2004
Cited alongside, same era.
Adversary lower bounds for nonadaptive quantum algorithms
P. Koiran, J. Landes, N. Portier, and P. Yao · 2010
Later among the works it cites.
Nonadaptive quantum query complexity
A. Montanaro · 2010
Later among the works it cites.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy · 2011
Later among the works it cites.
Learning-graph-based quantum algorithm for k k -distinctness
A. Belovs · 2012
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The quantum query complexity of the hidden subgroup problem is polynomial
M. Ettinger, P. Høyer, and E. Knill · 2004
Cited alongside, same era.
Equivalences and separations between quantum and classical learnability
R. A. Servedio and S. J. Gortler · 2004
Cited alongside, same era.
Improved bounds on quantum learning algorithms
A. Atıcı and R. A. Servedio · 2005
Cited alongside, same era.
All quantum adversary methods are equivalent
R. Špalek and M. Szegedy · 2006
Cited alongside, same era.
Quantum algorithms for learning and testing juntas
A. Atıcı and R. A. Servedio · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Cited alongside, same era.
A. Belovs · 2012
Later among the works it cites.
Span programs and quantum algorithms for s t st -connectivity and claw detection
A. Belovs and B. W. Reichardt · 2012
Later among the works it cites.
Quantum counterfeit coin problems
K. Iwama, H. Nishimura, R. Raymond, and J. Teruyama · 2012
Later among the works it cites.
Span-program-based quantum algorithm for evaluating formulas
B. W. Reichardt and R. Špalek · 2012
Later among the works it cites.
Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
B. Zhan, S. Kimmel, and A. Hassidim · 2012
Later among the works it cites.
Easy and hard functions for the boolean hidden shift problem
A. M. Childs, R. Kothari, M. Ozols, and M. Rötteler · 2013
Closest in time.
Improved quantum query algorithms for triangle finding and associativity testing
T. Lee, F. Magniez, and M. Santha · 2013
Closest in time.
Quantum algorithms for search with wildcards and combinatorial group testing
A. Ambainis and A. Montanaro · 2014
Closest in time.
On the power of non-adaptive learning graphs
A. Belovs and A. Rosmanis · 2014
Closest in time.
An optimal quantum algorithm for the oracle identification problem
R. Kothari · 2014
Closest in time.