Testing for forbidden order patterns in an array. Issue 2 (17th January 2019) - Newman, Ilan; Rabinovich, Yuri; Rajendraprasad, Deepak; Sohler, Christian
Abstract : A sequence f : [ n ] → R contains a pattern π ∈ S k, that is, a permutations of [ k ], iff there are indices i 1 < … < i k, such that f ( i x ) > f ( i y ) whenever π ( x ) > π ( y ). Otherwise, f is π ‐free. We study the property testing problem of distinguishing, for a fixed π, between π ‐free sequences and the sequences which differ from any π ‐free sequence in more than ϵ n places. Our main findings are as follows: (1) For monotone patterns, that is, π = ( k, k − 1, …, 1) and π = (1, 2, …, k ), there exists a nonadaptive one‐sided error ϵ ‐test of ( ϵ − 1 log n ) O ( k 2 ) query complexity. For any other π, any nonadaptive one‐sided error test requires Ω ( n ) queries. The latter lower‐bound is tight for π = (1, 3, 2). For specific π ∈ S k it can be strengthened to Ω( n 1 − 2/( k + 1) ). The general case upper‐bound is O ( ϵ −1/ k n 1 − 1/ k ). (2) For adaptive testing the situation is quite different. In particular, for any π ∈ S 3 there exists an adaptive ϵ ‐tester of ( ϵ − 1 log n ) O ( 1 ) query complexity.