文章基本信息

标题：Optimal bounds for monotonicity and Lipschitz testing over the hypercube
本地全文：下载
作者：Deeparnab Chakrabarty ; C. Seshadhri
期刊名称：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.
关键词：Monotonicity, Property Testing