TY - JOUR

T1 - Monotonicity testing over general poset domains

AU - Fischer, Eldar

AU - Lehman, Eric

AU - Newman, Ilan

AU - Raskhodnikova, Sofya

AU - Rubinfeld, Ronitt

AU - Samorodnitsky, Alex

N1 - Funding Information:
The authors would like to thank the Thailand Research Fund (TRF) for kind support (IRG 5780016). This research was also funded in part by grants from the Higher Education Research Promotion National Research University Project of Thailand, Office of the Higher Education Commission through the Health Cluster (SHeP-GMS), Thailand; the Faculty of Medicine, Khon Kaen University grant number TR57201; and the TRF Senior Research Scholar Grant, Thailand Research Fund grant number RTA5880001.

PY - 2002

Y1 - 2002

N2 - 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,⋯,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.

AB - 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,⋯,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.

UR - http://www.scopus.com/inward/record.url?scp=0036039104&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036039104&partnerID=8YFLogxK

U2 - 10.1145/509907.509977

DO - 10.1145/509907.509977

M3 - Conference article

AN - SCOPUS:0036039104

SP - 474

EP - 483

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

T2 - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

Y2 - 19 May 2002 through 21 May 2002

ER -