New algorithms and lower bounds for monotonicity testing

Probabilistic computations: Towards a unified measure of complexity

Original

Andrew Yao · 1977

Earlier work this paper cites.

Testing monotonicity

Oded Goldreich, Shafi Goldwasser, Eric Lehman, and Dana Ron · 1998

Earlier work this paper cites.

Improved testing algorithms for monotonocity

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky · 1999

Earlier work this paper cites.

Spot-checkers

Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, and Mahesh Vishwanthan · 2000

Earlier work this paper cites.

Testing monotonicity

Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samordinsky · 2000

Earlier work this paper cites.

Monotonicity testing over general poset domains

Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky · 2002

Earlier work this paper cites.

Sublinear algorithms for testing monotone and unimodal distributions

Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld · 2004

Earlier work this paper cites.

On the strength of comparisons in property testing

Eldar Fischer · 2004

Earlier work this paper cites.

Estimating the distance to a monotone function

Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu · 2007

Earlier work this paper cites.

Testing monotonicity over graph products

Shirley Halevy and Eyal Kushilevitz · 2008

Cited alongside, same era.

Gaussian bounds for noise correlation of functions and tight analysis of Long Codes

Elchanan Mossel · 2008

Cited alongside, same era.

Testing ± \pm 1-weight halfspaces

Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco Servedio · 2009

Cited alongside, same era.

Testing monotone high-dimensional distributions

Ronitt Rubinfeld and Rocco A. Servedio · 2009

Cited alongside, same era.

Lower bounds for testing function isomorphism

Eric Blais and Ryan O’Donnell · 2010

Cited alongside, same era.

Fooling functions of halfspaces under product distributions

Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman · 2010

Cited alongside, same era.

Monotonicity testing and shortest-path routing on the cube

Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah · 2012

Later among the works it cites.

Approximating the influence of monotone Boolean functions in O ⁡ ( n ) {O}(\sqrt{n}) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, and Omri Weinstein · 2012

Later among the works it cites.

Lower bounds for testing properties of functions on hypergrid domains

Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev · 2013

Later among the works it cites.

A o ⁡ ( n ) o(n) monotonicity tester for boolean functions over the hypercube

Deeparnab Chakrabarty and C. Seshadhri · 2013

Later among the works it cites.

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

Deeparnab Chakrabarty and C. Seshadhri · 2013

Later among the works it cites.

An optimal lower bound for monotonicity testing over hypergrids