Premium
Testing for forbidden order patterns in an array
Author(s) -
Newman Ilan,
Rabinovich Yuri,
Rajendraprasad Deepak,
Sohler Christian
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20840
Subject(s) - property testing , combinatorics , sequence (biology) , upper and lower bounds , monotone polygon , order (exchange) , mathematics , existential quantification , property (philosophy) , discrete mathematics , group testing , mathematical analysis , philosophy , genetics , geometry , finance , epistemology , economics , biology
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 kit 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 3there exists an adaptive ϵ ‐tester of( ϵ − 1 log n ) O ( 1 )query complexity.