  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 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/\eps)$ samples suffice for the edge tester. For hypergrids, known testers
require $O(\eps^{-1}n\log k\log |\R|)$ samples, while the best known
(non-adaptive) lower bound is $\Omega(\eps^{-1} n\log k)$. We give a
(non-adaptive) monotonicity tester for hypergrids running in $O(\eps^{-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(\eps^{-1}n\log k)$-query testers for a
class of "bounded-derivative" properties, a class containing both monotonicity
and Lipschitz.
