Fetching the paper…
Reading the bibliography…
Adaptivity is known to play a crucial role in property testing.
Communication complexity
Christos H. Papadimitriou and Michael Sipser · 1982
Earlier work this paper cites.
Self-testing/correcting with applications to numerical problems
Manuel Blum, Michael Luby, and Ronitt Rubinfeld · 1993
Earlier work this paper cites.
Rounds in communication complexity revisited
Noam Nisan and Avi Wigderson · 1993
Earlier work this paper cites.
Robust characterization of polynomials with applications to program testing
Ronitt Rubinfeld and Madhu Sudan · 1996
Earlier work this paper cites.
Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron · 1998
Earlier work this paper cites.
Efficient testing of large graphs
Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy · 2000
Earlier work this paper cites.
Combinatorial Group Testing and Its Applications
Dingzhu Du and Frank K. Hwang · 2000
Earlier work this paper cites.
On testing expansion in bounded-degree graphs
Oded Goldreich and Dana Ron · 2000
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Three theorems regarding testing graph properties
Oded Goldreich and Luca Trevisan · 2003
Earlier work this paper cites.
Some 3CNF properties are hard to test
Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova · 2005
Earlier work this paper cites.
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan · 2006
Earlier work this paper cites.
A note on adaptivity in testing properties of bounded degree graphs
Sofya Raskhodnikova and Adam D. Smith · 2006
Earlier work this paper cites.
Algebrization: a new barrier in complexity theory
Scott Aaronson and Avi Wigderson · 2008
Cited alongside, same era.
Improved bounds for testing juntas
Eric Blais · 2008
Cited alongside, same era.
Property testing: A learning theory perspective
Dana Ron · 2008
Cited alongside, same era.
Testing juntas nearly optimally
Eric Blais · 2009
Cited alongside, same era.
Testing ± \pm 1-weight halfspace
Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio · 2009
Cited alongside, same era.
Algorithmic and analysis techniques in property testing
Dana Ron · 2009
Cited alongside, same era.
Property Testing - Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010]
The non-adaptive query complexity of testing k k -parities
Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf · 2013
Later among the works it cites.
On the communication complexity methodology for proving lower bounds on the query complexity of property testing
Oded Goldreich · 2013
Later among the works it cites.
Exponentially improved algorithms and lower bounds for testing signed majorities
Dana Ron and Rocco A. Servedio · 2013
Later among the works it cites.
On the communication complexity of sparse set disjointness and exists-equal problems
Mert Sağlam and Gábor Tardos · 2013
Later among the works it cites.
Property testing bounds for linear and quadratic functions via parity decision trees
Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Oded Goldreich, editor · 2010
Cited alongside, same era.
Lower bounds for testing computability by small width OBDDs
Joshua Brody, Kevin Matulef, and Chenggang Wu · 2011
Cited alongside, same era.
Algorithmic aspects of property testing in the dense graphs model
Oded Goldreich and Dana Ron · 2011
Cited alongside, same era.
On the power of adaptivity in sparse recovery
Piotr Indyk, Eric Price, and David P. Woodruff · 2011
Cited alongside, same era.
Property testing lower bounds via communication complexity
Eric Blais, Joshua Brody, and Kevin Matulef · 2012
Cited alongside, same era.
Tight bounds for testing k k -linearity
Eric Blais and Daniel M. Kane · 2012
Cited alongside, same era.
Roei Tell · 2014
Later among the works it cites.
A Survey on Distribution Testing: your data is Big. But is it Blue?
Clément L. Canonne · 2015
Later among the works it cites.
Strong locally testable codes with relaxed local decoders
Oded Goldreich, Tom Gur, and Ilan Komargodski · 2015
Later among the works it cites.
Adaptivity helps for testing juntas
Rocco A. Servedio, Li-Yang Tan, and John Wright · 2015
Later among the works it cites.
Property Testing
Arnab Bhattacharyya and Yuichi Yoshida · 2017
Closest in time.
Settling the query complexity of non-adaptive junta testing
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie · 2017
Closest in time.
Introduction to Property Testing
Oded Goldreich · 2017
Closest in time.
A hierarchy theorem for interactive proofs of proximity
Tom Gur and Ron D. Rothblum · 2017
Closest in time.