Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries

The Classical Moment Problem

Naum Akhiezer · 1965

Earlier work this paper cites.

An introduction to probability theory and its applications

William Feller · 1968

Earlier work this paper cites.

On subspaces spanned by random selections of ± 1 \pm 1 vectors

Andrew Odlyzko · 1988

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.

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.

On the dependence of the Berry–Esseen bound on dimension

Vidmantas Bentkus · 2003

Cited alongside, same era.

Information theory in property testing and monotonicity testing in higher dimension

N. Ailon and B. Chazelle · 2006

Cited alongside, same era.

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.

Fooling functions of halfspaces under product distributions

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

Cited alongside, same era.

On the exact space complexity of sketching and streaming small norms

Daniel Kane, Jelani Nelson, and David Woodruff · 2010

Cited alongside, same era.

Testing halfspaces

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

Later among the works it cites.

Estimating the unseen: an n / log ⁡ ( n ) n/\log(n) -sample estimator for entropy and support size, shown optimal via new CLTs

Gregory Valiant and Paul Valiant · 2011

Later among the works it cites.

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.

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.

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry

Original

Anindya De, Ilias Diakonikolas, and Rocco A. Servedio · 2013

Later among the works it cites.