Testing Monotonicity

We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f: {0, 1}/sup n/-{0, 1} at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is /spl epsiv/-far from being monotone (i. e. , every monotone function differs from f on more than an /spl epsiv/ fraction of the domain). The complexity of the test is poly(n//spl epsiv/). 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. We also consider the problem of testing monotonicity based only on random examples labeled by the function. We show an /spl Omega/(/spl radic/2/sup n///spl epsiv/) lower bound on the number of required examples, and provide a matching upper bound (via an algorithm).

Authors

• Oded Goldreich 0001
• Shafi Goldwasser
• Eric Lehman
• Dana Ron

Keywords

• Testing
• Computer science
• Postal services
• Gold
• Algorithm design and analysis
• Lab-on-a-chip
• Upper bound
• Electrical capacitance tomography
• Mathematics
• Laboratories
• Boolean Function
• Fraction Of Domains
• Value Function
• Time Complexity
• Set Of Elements
• Pathfinding
• Out-degree
• Forward Error Correction
• Nature Of Representations
• Representative Subset
• Concept Of Class
• Subset Of Vertices
• Fraction Of Pairs