Testing Monotonicity |
| |
| Authors: | Oded Goldreich Shafi Goldwasser Eric Lehman Dana Ron Alex Samorodnitsky |
| |
| Affiliation: | (1) Department of Computer Science and Applied Mathematics, Weizmann Institute of Science; Rehovot, Israel; E-mail: oded@wisdom.weizmann.ac.il, IL;(2) Laboratory for Computer Science, MIT; 545 Technology Sq., Cambridge, MA 02139, USA; E-mail: shafi@theory.lcs.mit.edu, US;(3) Laboratory for Computer Science, MIT; 545 Technology Sq., Cambridge, MA 02139, USA; E-mail: e_lehman@theory.lcs.mit.edu, US;(4) Department of EE – Systems, Tel Aviv University; Ramat Aviv, Israel; E-mail: danar@eng.tau.ac.il, IL;(5) School of Mathematics, Institute for Advanced Study; Olden Lane, Princeton, NJ 08540, USA; E-mail: asamor@ias.edu, US |
| |
| Abstract: | at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). 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. Received March 29, 1999 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 68Q25, 68R05, 68Q05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
