An Õ(n) Queries Adaptive Tester for Unateness
An Õ(n) Queries Adaptive Tester for Unateness
复制标题
Õ(n) 查询自适应测试器是否不相符
DOI：
10.4230/lipics.approx-random.2016.37
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Igor Shinkar
中科院分区：
文献类型：
--
作者：
Subhash Khot;Igor Shinkar
我们提出了一种布尔函数统一性属性的自适应测试器。给定函数 f:{0,1}^n -> {0,1}，测试器对函数进行 O(n log(n)/epsilon) 自适应查询。测试者总是接受单义函数，如果函数离单义函数有epsilon距离，则拒绝概率至少为 0.9。
We present an adaptive tester for the unateness property of Boolean functions. Given a function f:{0,1}^n -> {0,1} the tester makes O(n log(n)/epsilon) adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is epsilon-far from being unate.