Improved Algorithm for Permutation Testing

For a permutation $\pi :[K]\to [K]$, a sequence $f: {1,2,\cdots, n}\rightarrow \mathbb R$containsa$\pi$-patternofsize$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 $\pi (a)<\pi (b)$, for $a,b\in [K]$. Otherwise, $f$ is referred to as $\pi$-free. For the special case where $\pi = (1,2,\cdots, K)$, it is referred to as the monotone pattern. \cite{newman2017testing} initiated the study of testing $\pi$-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-adaptivequerycomplexityof\text{cite}newman2017testingto$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.