## Testing Monotinicity

#### Webpage for a paper by Goldreich, Goldwasser, Lehman, Ron,
and Samorodnitsky

#### Abstract

We present a (randomized) test for monotonicity of Boolean functions.
Namely, given the ability to query an unknown
function $f:\bitset^n\to\bitset$ at arguments of its choice,
the test always accepts a monotone $f$,
and rejects $f$ with high probability if it is $epsilon$-far
from being monotone (i.e., every monotone function differs from $f$
on more than an $epsilon$ fraction of the domain).
The complexity of the test is $O(n/epsilon)$.

The analysis of our algorithm relates two natural combinatorial quantities
that can be measured with respect to a Boolean function;
one being global to the function and the other being local to it.
A key ingredient is the use of a *switching*
(or *sorting*) operator on functions.

#### Material available on-line

- Goldreich, Goldwasser, and Ron:
a note
on testing monotinicity (leaving an open problem), 1997.
- Goldreich, Goldwasser, Lehman, and Ron:
a
write-up that resolves the open problem and more, 1998.
- Goldreich, Goldwasser, Lehman, Ron, and Samorodnitsky:
an
improved version, 1999.

#### Related Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.