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

Related Material available on-line


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