Random Structures & Algorithms

Testing for forbidden order patterns in an array

Early View

A sequence contains a pattern , 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 query complexity. For any other π, any nonadaptive one‐sided error test requires queries. The latter lower‐bound is tight for π = (1,3,2). For specific 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 there exists an adaptive ϵ‐tester of query complexity.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.