Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 10 (2014) Article 17 pp. 453-464
An Optimal Lower Bound for Monotonicity Testing over Hypergrids
Received: April 2, 2014
Revised: December 3, 2014
Published: December 24, 2014
Download article from ToC site:
[PDF (235K)] [PS (815K)] [Source ZIP]
Keywords: lower bounds, property testing, monotonicity testing
ACM Classification: K.4.1, I.2.6, F.2.0
AMS Classification: 68Q32, 68Q25, 68W20

Abstract: [Plain Text Version]

\newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb{N}}

For positive integers n, d, the hypergrid [n]^d is equipped with the coordinatewise product partial ordering denoted by \prec. A function f: [n]^d \to \NN is monotone if \forall x \prec y, f(x) \leq f(y). A function f is \eps-far from monotone if at least an \eps fraction of values must be changed to make f monotone. Given a parameter \eps, a monotonicity tester must distinguish with high probability a monotone function from one that is \eps-far.

We prove that any (adaptive, two-sided) monotonicity tester for functions f:[n]^d \to \NN must make \Omega(\eps^{-1}d\log n - \eps^{-1}\log \eps^{-1}) queries. Recent upper bounds show the existence of O(\eps^{-1}d \log n) query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of \Omega(d \log n).

A conference version of this paper appeared in the Proceedings of the 17th Internat. Workshop o Randomization and Computation (RANDOM 2013).