2017/10/29 by Omri Ben-Eliezer, Clément L. Canonne, Ben-Eliezer, Omri +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1710.10660
arxiv created 2017/10/29 · arxiv updated 2017/10/31
A sequence f\colon\1,…,n\→ℝ contains a permutation π of length k if there exist i1<…<ik such that, for all x,y, f(ix)<f(iy) if and only if π(x)<π(y); otherwise, f is said to be π-free. In this work, we consider the problem of testing for π-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 ε-test for π-freeness making Θ(ε-1/k n1-1/k) queries, our lower bounds imply that this is almost optimal for most permutations! Specifically, for most permutations π of length k, any non-adaptive one-sided ε-test requires ε-1/(k-Θ(1))n1-1/(k-Θ(1)) queries; furthermore, the permutations that are hardest to test require Θ(ε-1/(k-1)n1-1/(k-1)) queries, which is tight in n and ε. Additionally, we show two hierarchical behaviors here. First, for any k and l≤ k-1, there exists some π of length k that requires Θε(n1-1/l) non-adaptive queries. Second, we show an adaptivity hierarchy for π=(1,3,2) by proving upper and lower bounds for (one- and two-sided) testing of π-freeness with r rounds of adaptivity. The results answer open questions of Newman et al. and [Canonne and Gur, CCC'17].