Improved bounds for testing forbidden order patterns

MaRDI QIDQ4608030zbMATH OpenFDO

Authors Omri Ben-Eliezer, Clement L. Canonne

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1710.10660, http://dl.acm.org/citation.cfm?id=3175442

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Abstract: A sequence $fcolon1,dots,nomathbbR$ contains a permutation $pi$ of length $k$ if there exist $i_1<dots<i_k$ such that, for all $x,y$, $f(i_x)<f(i_y)$ if and only if $pi(x)<pi(y)$; otherwise, $f$ is said to be $pi$-free. In this work, we consider the problem of testing for $pi$-freeness with one-sided error, continuing the investigation of [Newman et al., SODA'17]. We demonstrate a surprising behavior for non-adaptive tests with one-sided error: While a trivial sampling-based approach yields an $varepsilon$-test for $pi$-freeness making $Theta(varepsilo{n}^{-1/k}{n}^{1-1/k})$ queries, our lower bounds imply that this is almost optimal for most permutations! Specifically, for most permutations $pi$ of length $k$, any non-adaptive one-sided $varepsilon$-test requires $varepsilo{n}^{-1/(k-Theta(1))}{n}^{1-1/(k-Theta(1))}$ queries; furthermore, the permutations that are hardest to test require $Theta(varepsilo{n}^{-1/(k-1)}{n}^{1-1/(k-1)})$ queries, which is tight in $n$ and $varepsilon$. Additionally, we show two hierarchical behaviors here. First, for any $k$ and $lleqk-1$, there exists some $pi$ of length $k$ that requires $ilde{Theta}_{varepsilon}(n^{1-1/l})$ non-adaptive queries. Second, we show an adaptivity hierarchy for $pi=(1,3,2)$ by proving upper and lower bounds for (one- and two-sided) testing of $pi$-freeness with $r$ rounds of adaptivity. The results answer open questions of Newman et al. and [Canonne and Gur, CCC'17].

Recommendations

• Testing for forbidden order patterns in an array
• Testing for forbidden order patterns in an array
• On the strength of comparisons in property testing
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Property testing and parameter testing for permutations

Cited in

(10)

• Finding and counting permutations via CSPs
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Testing for forbidden order patterns in an array
• Testing for forbidden posets in ordered rooted forests
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing for forbidden order patterns in an array
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Improved algorithm for permutation testing
• Strongly sublinear algorithms for testing pattern freeness

This page was built for publication: Improved bounds for testing forbidden order patterns

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