Improved algorithm for permutation testing

DOI10.1016/J.TCS.2023.114316arXiv2006.08473OpenAlexW4388948151MaRDI QIDQ6138826FDOQ6138826

Authors:

Publication date: 16 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A sequence $f:1,2,cdots,nightarrowmathbbR$ contains a $pi$-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 $pi(a)<pi(b)$, for $a,bin[k]$. Otherwise, $f$ is referred to as $pi$-free. cite{newman2017testing} initiated the study of testing $pi$-freeness with one-sided error. They focused on two special cases, the monotone permutations and the $(1,3,2)$ permutation. cite{ben2019finding} improved the $(logn{)}^{O(k^2)}$ non-adaptive query complexity of cite{newman2017testing} to $O((logn{)}^{lfloorlo{g}_{2}kfloor})$. Further, cite{ben2019optimal} proposed an adaptive algorithm with $O(logn)$ query complexity. However, no progress has yet been made on the problem of testing $(1,3,2)$-pattern. In this work, we present an adaptive algorithm for testing $(1,3,2)$-pattern. The query complexity of our algorithm is $O(epsilo{n}^{-2}lo{g}^{4}n)$, which significantly improves over the $O(epsilo{n}^{-7}lo{g}^{26}n)$-query adaptive algorithm of cite{newman2017testing}. This improvement is mainly achieved by the proposal of a new structure embedded in the patterns.

Full work available at URL: https://arxiv.org/abs/2006.08473

zbMATH Keywords

property testingpermutation testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Spot-checkers
• Title not available (Why is that?)
• Estimating the distance to a monotone function
• Finding small patterns in permutations in linear time
• Estimating the sortedness of a data stream
• On the strength of comparisons in property testing
• Monotonicity testing and shortest-path routing on the cube
• Property testing lower bounds via communication complexity
• Tolerant property testing and distance approximation
• Testing for forbidden order patterns in an array
• Estimating the longest increasing sequence in polylogarithmic time
• Improved bounds for testing forbidden order patterns
• An optimal lower bound for monotonicity testing over hypergrids
• Parameterized property testing of functions
• A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
• Adaptive lower bound for testing monotonicity on the line

This page was built for publication: Improved algorithm for permutation testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138826)