文章基本信息

标题：A {\huge o(n) } monotonicity tester for Boolean functions over the hypercube
本地全文：下载
作者：Deeparnab Chakrabarty ; C. Seshadhri
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2013
卷号：2013
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：
Given oracle access to a Boolean function f:01n01 , we design a randomized tester that takes as input a parameter 0">\eps0, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability 2/3">23 , if the function is \eps-far from monotone. That is, f needs to be modified at \eps-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes O(n78\eps−32) queries to the oracle.
关键词：Monotonicity testing; Property Testing; Random Walks