Fetching the paper…
Reading the bibliography…
In the $k$-junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$-junta (i.e., depends on at most $k$ of its input bits) or is $\epsilon$-far from any $k$-junta.
The detection of defective members of large populations
R. Dorfman · 1943
Earlier work this paper cites.
Distribution inequalities for the binomial law
E. V. Slud · 1977
Earlier work this paper cites.
Mean, median and mode in binomial distributions
R. Kaas and J. Buhrman · 1980
Earlier work this paper cites.
Combinatorial group testing and its applications
D. Z. Du and F. Hwang · 1993
Earlier work this paper cites.
Quantum measurements and the Abelian stabilizer problem
A. Kitaev · 1995
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Quantum computation of Fourier transforms over symmetric groups
R. Beals · 1997
Earlier work this paper cites.
Communication Complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum cryptanalysis of hash and claw-free functions
G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
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
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Earlier work this paper cites.
A lower bound for testing juntas
H. Chockler and D. Gutfreund · 2004
Earlier work this paper cites.
Testing juntas
E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky · 2004
Earlier work this paper cites.
Efficient quantum circuits for Schur and Clebsch-Gordan transforms
D. Bacon, I. Chuang, and A. Harrow · 2006
Cited alongside, same era.
Generic quantum Fourier transforms
C. Moore, D. Rockmore, and A. Russell · 2006
Cited alongside, same era.
Quantum algorithms for learning and testing juntas
A. Atıcı and R. A. Servedio · 2007
Cited alongside, same era.
The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits
D. Bacon, I. Chuang, and A. Harrow · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Cited alongside, same era.
Classical and quantum algorithms for exponential congruences
An optimal lower bound on the communication complexity of gap Hamming distance
A. Chakrabarti and O. Regev · 2012
Later among the works it cites.
Query-Efficient Computation in Property Testing and Learning Theory
D. García-Soriano · 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.
How to construct quantum random functions
M. Zhandry · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
W. van Dam and I. E. Shparlinski · 2008
Cited alongside, same era.
Testing juntas nearly optimally
E. Blais · 2009
Cited alongside, same era.
Strong lower bounds for approximating distribution support size and the distinct elements problem
S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith · 2009
Cited alongside, same era.
B. W. Reichardt · 2009
Cited alongside, same era.
Bounds for nonadaptive group tests to estimate the amount of defectives
P. Damaschke and A. S. Muhammad · 2010
Cited alongside, same era.
Property Testing: Current Research and Surveys
O. Goldreich, editor · 2010
Cited alongside, same era.
Property testing lower bounds via communication complexity
E. Blais, J. Brody, and K. Matulef · 2011
Cited alongside, same era.
A. Belovs · 2013
Later among the works it cites.
Adversary lower bounds for the collision and the set equality problems
A. Belovs and A. Rosmanis · 2013
Later among the works it cites.
Quantum Fourier transform over symmetric groups
Y. Kawano and H. Sekigawa · 2013
Later among the works it cites.
An efficient FPRAS type group testing procedure to approximate the number of defectives
Y. Cheng and Y. Xu · 2014
Later among the works it cites.
Quantum Fourier transform over symmetric groups: Improved result
Y. Kawano and H. Sekigawa · 2014
Later among the works it cites.
Separations in query complexity based on pointer functions
A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs · 2015
Closest in time.
Quantum algorithms for learning symmetric juntas via the adversary bound
A. Belovs · 2015
Closest in time.
Variations on quantum adversaries
A. Belovs · 2015
Closest in time.
Quantum algorithm for monotonicity testing on the hypercube
A. Belovs and E. Blais · 2015
Closest in time.
A super-Grover separation between randomized and quantum query complexities
S. Ben-David · 2015
Closest in time.
Adaptivity helps for testing juntas
R. A. Servedio, L.-Y. Tang, and J. Wright · 2015
Closest in time.
A note on the quantum collision and set equality problems
M. Zhandry · 2015
Closest in time.
A survey of quantum property testing
A. Montanaro and R. de Wolf · 2035
Closest in time.