Computer Science – Discrete Mathematics
Scientific paper
2012-04-04
Computer Science
Discrete Mathematics
Scientific paper
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 $\cB^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 $\cB^n$, $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. It is known that the edge tester using $O(n\log |R|/\eps)$ samples can distinguish a monotone function from one where $\eps_f > \eps$. 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/\eps)$ 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.
Chakrabarty Deeparnab
Seshadhri C.
No associations
LandOfFree
Optimal bounds for monotonicity and Lipschitz testing over the hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal bounds for monotonicity and Lipschitz testing over the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal bounds for monotonicity and Lipschitz testing over the hypercube will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-31313