Revision #2 Authors: Deeparnab Chakrabarty, C. Seshadhri

Accepted on: 19th March 2014 00:17

Downloads: 679

Keywords:

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;

Revision #1 Authors: Deeparnab Chakrabarty, C. Seshadhri

Accepted on: 7th November 2012 23:08

Downloads: 1447

Keywords:

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

TR12-030 Authors: Deeparnab Chakrabarty, C. Seshadhri

Publication: 4th April 2012 13:31

Downloads: 1417

Keywords:

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.