Improved Testing Algorithms for Monotonicity
Improved Testing Algorithms for Monotonicity
复制标题
改进的单调性测试算法
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Alex Samorodnitsky
中科院分区：
文献类型：
--
作者：
Y. Dodis;Oded Goldreich;E. Lehman;Sofya Raskhodnikova;D. Ron;Alex Samorodnitsky
我们提出了用于测试函数单调性的算法。如果是单调的E-FAR（即，对于任何E> 0，在域的E e> 0以外，每个单调函数差异）。 log ∣σ vert）\）。
We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: Σ n ↦ Ξ, where Σ and Ξ are finite ordered sets, the test always accepts a monotone f, and rejects f with high probability if it is e-far from being monotone (i.e., every monotone function differs from f on more than an e fraction of the domain). For any e > 0, the query complexity of the test is O((n/e) · log ∣Σ ∣ · log ∣Ξ∣). The previous best known bound was \(\tilde{O}((n^2/\epsilon) \cdot \vert\Sigma\vert^2 \cdot \vert\Xi\vert)\).