Next: Deterministic Amplification of Space
Up: Sabbatical at MIT (1996-1998)
Previous: Honest-Verifier Statistical Zero-Knowledge Equals
This work presents a (randomized) test for monotonicity of Boolean
functions (i.e., mapping n-bit strings to a single bit).
By querying the function at arguments of its choice,
the test always accepts a monotone function,
and rejects with high probability any function that is far
from being monotone. The query complexity of the test is linear
in n and in the inverse of the distance parameter.
Comments:
Authored by O. Goldreich, S. Goldwasser, E. Lehman and D. Ron. Appeared in
- Proc. of the 39th FOCS, pages 426-435, 1998.
- Journal
version with A. Samorodnitsky,
Combinatorica, Vol. 20 (3), pages 301-337, 2000.
Oded Goldreich
2003-07-30