Testing for forbidden order patterns in an array. Issue 2 (17th January 2019)

• Record Type: Journal Article
• Authors: Newman, Ilan; Rabinovich, Yuri; Rajendraprasad, Deepak; Sohler, Christian
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 402
• Page End: 426
• Publication Date: 2019-01-17
• Subjects: Property Testing -- Monotonicity Testing -- Non‐adaptive Testing -- Adaptive Testing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20840
• Languages: English
• ISSNs: 1042-9832

Abstract

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.