论文标题
改进的置换测试算法
Improved Algorithm for Permutation Testing
论文作者
论文摘要
对于排列$π：[k] \ rightarrow [k] $，序列$ f：\ {1,2，\ cdots，n \} \ rightarrow \ Mathbb r $包含一个$ k $的$π$ -pattern，如果有一系列$ k $，如果有一系列指数$（i_1，i_1，i_1，i_2，cdots $ cdots，i_2，cdots $ __k） （$ i_1 <i_2 <\ cdots <i_k $），满足$ f（i_a）<f（i_b）$，如果$π（a）<π（b）$，for $ a，b \ in [k] $。否则，$ f $称为$π$ - free。对于$π=（1,2，\ cdots，k）$的特殊情况，它称为单调图案。 \ cite {newman2017-Testing}启动了具有单方面错误的测试$π$ - fre。他们专注于两个特定问题，测试单调排列和$（1,3,2）$置换。对于测试单调置换的问题，$（1,2，\ cdots，k）$，\ cite {ben2019finding}改进了$（\ log n）^{o（k^2）} $非自动查询的复杂性， k \ rfloor}）$。此外，\ cite {ben2019optimal}提出了一种具有$ o（\ log n）$查询复杂性的自适应算法。但是，在测试$（1,3,2）$ - freeness的问题上尚未取得任何进展。在这项工作中，我们提出了一种自适应算法，用于测试$（1,3,2）$ - freeness。我们算法的查询复杂性为$ O（ε^{ - 2} \ log^4 n）$，它显着改善了$ O（ε^{ - 7} \ log^{26} n）$ - 查询自适应自适应算法\ cite {newman2017testing}。这种改进主要是通过嵌入模式中的新结构的建议来实现的。
For a permutation $π: [K]\rightarrow [K]$, a sequence $f: \{1,2,\cdots, n\}\rightarrow \mathbb R$ contains a $π$-pattern of size $K$, if there is a sequence of indices $(i_1, i_2, \cdots, i_K)$ ($i_1<i_2<\cdots<i_K$), satisfying that $f(i_a)<f(i_b)$ if $π(a)<π(b)$, for $a,b\in [K]$. Otherwise, $f$ is referred to as $π$-free. For the special case where $π= (1,2,\cdots, K)$, it is referred to as the monotone pattern. \cite{newman2017testing} initiated the study of testing $π$-freeness with one-sided error. They focused on two specific problems, testing the monotone permutations and the $(1,3,2)$ permutation. For the problem of testing monotone permutation $(1,2,\cdots,K)$, \cite{ben2019finding} improved the $(\log n)^{O(K^2)}$ non-adaptive query complexity of \cite{newman2017testing} to $O((\log n)^{\lfloor \log_{2} K\rfloor})$. Further, \cite{ben2019optimal} proposed an adaptive algorithm with $O(\log n)$ query complexity. However, no progress has yet been made on the problem of testing $(1,3,2)$-freeness. In this work, we present an adaptive algorithm for testing $(1,3,2)$-freeness. The query complexity of our algorithm is $O(ε^{-2}\log^4 n)$, which significantly improves over the $O(ε^{-7}\log^{26}n)$-query adaptive algorithm of \cite{newman2017testing}. This improvement is mainly achieved by the proposal of a new structure embedded in the patterns.
