文章基本信息
- 标题：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
