The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to f:[k]^n \mapsto \R
(for some ordered range \R).
The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by \prec.
A function is \emph{monotone} if for all pairs x \prec y,
f(x) \leq f(y). The distance to monotonicity, \eps_f, is the minimum fraction of values of f
that need to be changed to make f monotone.
For k=2 (the boolean hypercube), the usual tester is the \emph{edge tester}, which
checks monotonicity on adjacent pairs of domain points.
It is known that the edge tester using O(\eps^{-1}n\log|\R|)
samples can distinguish a monotone function from one where \eps_f > \eps.
On the other hand, the best lower bound for monotonicity testing over general \R is \Omega(n).
We resolve this long standing open problem and prove that O(n/\eps) samples suffice
for the edge tester. For hypergrids, existing testers require O(\eps^{-1}n\log k\log |\R|) samples.
We give
a (non-adaptive) monotonicity tester for hypergrids running in O(\eps^{-1} n\log k) time,
recently shown to be optimal.
Our techniques lead to optimal property testers (with the same running time) for the natural \emph{Lipschitz property}
on hypercubes and hypergrids. (A c-Lipschitz function
is one where |f(x) - f(y)| \leq c\|x-y\|_1.)
In fact, we give a general unified proof for O(\eps^{-1}n\log k)-query testers for a class of ``bounded-derivative" properties that contains both monotonicity and Lipschitz.

Better presentation and notation; much cleaner proofs;

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to f:[k]^n \mapsto R
(for some ordered range R). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by \prec. A function is \emph{monotone} if for all pairs x \prec y, f(x) \leq f(y). The distance to monotonicity, \varepsilon_f, is the minimum fraction of values of f
that need to be changed to make f monotone.

For k=2 (the boolean hypercube), the usual tester is the \emph{edge tester}, which
checks monotonicity on adjacent pairs of domain points.
It is known that the edge tester using O(\varepsilon^{-1}n\log|R|)
samples can distinguish a monotone function from one where \varepsilon_f > \varepsilon.
On the other hand, the best lower bound for monotonicity testing over the hypercube is \min(|R|^2,n).
This leaves
a quadratic gap in our knowledge, since |R| can be 2^n.
We resolve this long standing open problem and prove that O(n/\varepsilon) samples suffice
for the edge tester. For hypergrids, known testers require O(\varepsilon^{-1}n\log k\log |R|) samples, while
the best known (non-adaptive) lower bound is \Omega(\varepsilon^{-1} n\log k). We give
a (non-adaptive) monotonicity tester for hypergrids running in O(\varepsilon^{-1} n\log k) time.

Our techniques lead to optimal property testers (with the same running time) for the natural \emph{Lipschitz property}
on hypercubes and hypergrids. (A c-Lipschitz function
is one where |f(x) - f(y)| \leq c\|x-y\|_1.)
In fact, we give a general unified proof for O(\varepsilon^{-1}n\log k)-query testers for a class of ``bounded-derivative" properties,
a class containing both monotonicity and Lipschitz.

New results on hypergrids

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved
question in property testing. We are given query access to f:\{0,1\}^n \mapsto R
(for some ordered range R). The boolean hypercube {\cal B}^n has a natural partial order, denoted by \prec (defined by the product of
coordinate-wise ordering). A function is \emph{monotone} if all pairs x \prec y in {\cal B}^n,
f(x) \leq f(y). The distance to monotonicity, \varepsilon_f, is the minimum fraction of values of f
that need to be changed to make f monotone. It is known that the edge tester
using O(n\log |R|/\varepsilon) samples can distinguish a monotone function from one where \varepsilon_f > \varepsilon.
On the other hand, the best lower bound for monotonicity testing is \min(|R|^2,n). This leaves
a quadratic gap in our knowledge, since |R| can be 2^n.

We prove that the edge tester only requires O(n/\varepsilon) samples (regardless of R), resolving this question.
Our technique is quite general, and we get optimal edge testers for the Lipschitz property.
We prove a very general theorem showing that edge testers work for a class of ``bounded-derivative"
properties, which contains both monotonicity and Lipschitz.