Monotonicity testing over general poset domains
Authors:
Open Access
- 19 May 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 474-483
Abstract
The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are `far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube {1,&ldots;,m}n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.Keywords
This publication has 10 references indexed in Scilit:
- Testing of matrix properties2001
- Regular Languages are Testable with a Constant Number of QueriesSIAM Journal on Computing, 2001
- The Probabilistic Method2000
- Spot-CheckersJournal of Computer and System Sciences, 2000
- Efficient Testing of Large GraphsCombinatorica, 2000
- Testing MonotonicityCombinatorica, 2000
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Property testing in bounded degree graphs1997
- Robust Characterizations of Polynomials with Applications to Program TestingSIAM Journal on Computing, 1996
- On Sets of Integers Which Contain No Three Terms in Arithmetical ProgressionProceedings of the National Academy of Sciences, 1946