Header menu link for other important links
X

Testing for forbidden order patterns in an array

Ilan Newman, Yuri Rabinovich, , Christian Sohler
Published in
2019
Abstract

A sequence urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0001 contains a pattern urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0002, that is, a permutations of [k], iff there are indices i1 < … < ik, such that f(ix) > f(iy) 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 urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0003 query complexity. For any other π, any nonadaptive one-sided error test requires urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0004 queries. The latter lower-bound is tight for π = (1,3,2). For specific urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0005 it can be strengthened to Ω(n1 − 2/(k + 1)). The general case upper-bound is O(ϵ−1/kn1 − 1/k). (2) For adaptive testing the situation is quite different. In particular, for any urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0006 there exists an adaptive ϵ-tester of urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0007 query complexity.

About the journal
Open AccessNo