期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved
question in property testing. We are given query access to f:01nR
(for some ordered range R). The boolean hypercube n has a natural partial order, denoted by (defined by the product of
coordinate-wise ordering). A function is \emph{monotone} if all pairs xy in n,
f(x)f(y). The distance to monotonicity, f, is the minimum fraction of values of f
that need to be changed to make f monotone. It is known that the edge tester
using O(nlogR) samples can distinguish a monotone function from one where f.
On the other hand, the best lower bound for monotonicity testing is min(R2n) . This leaves
a quadratic gap in our knowledge, since R can be 2n.
