Improved Bounds for Testing Forbidden Order Patterns

Omri Ben-Eliezer, Clément L. Canonne

TL;DR

This paper investigates the problem of "testing for forbidden order patterns" in sequences, a fundamental problem in property testing. The authors establish new, tight bounds on the number of queries required for such tests, revealing surprising behaviors and hierarchies related to the structure of the forbidden patterns and the adaptivity of the testing algorithms.

What Problem Does This Paper Address?

The core problem is property testing, specifically testing if a sequence of numbers avoids a particular "forbidden order pattern." Imagine you have a long sequence of numbers, and you want to know if it contains a specific arrangement of relative orderings (like a "1, 3, 2" pattern, meaning the first element is smaller than the third, which is smaller than the second). You don't want to look at the whole sequence; you want an efficient algorithm that can tell you if the sequence avoids this pattern or is "far" from avoiding it (meaning you'd have to change many numbers to make it avoid the pattern).

This paper focuses on one-sided error tests, meaning the algorithm is guaranteed to say "yes" if the sequence is truly pattern-free, but might err if it's far from pattern-free. The challenge is to understand how the complexity of this testing problem (how many numbers we need to look at) depends on the length of the sequence, the complexity of the forbidden pattern, and whether the testing algorithm can adapt its queries based on previous answers. Previous work had established some bounds, but a complete understanding, especially for non-monotone patterns and varying levels of adaptivity, was missing.

Methods

The paper introduces several key techniques and findings:

  • Improved Upper Bounds: They develop new algorithms that provide better upper bounds on the number of queries needed for non-adaptive tests, especially for complex patterns.
  • Permutation-Dependent Lower Bounds: A central contribution is a general lower bound that explicitly depends on the structure of the forbidden permutation. This is achieved by constructing specific "hard" sequences that are designed to be difficult to test.
  • Unique Signed Partitions (USPN): A novel combinatorial quantity, the USPN, is introduced and shown to be crucial in determining the testing complexity. This quantity captures structural properties of permutations that make them hard to test.
  • Adaptivity Hierarchy: For a specific pattern (1,3,2), they demonstrate that adding more "rounds" of adaptivity (where the algorithm can make decisions based on previous answers) significantly reduces the number of queries required. This is a significant finding, as it's the first natural example of such a hierarchy for a single property.
  • Reduction Techniques: To prove lower bounds for adaptivity, they employ a reduction from a problem called "TEMPLATE-SEARCH" to the (1,3,2)-freeness testing problem. This allows them to leverage existing lower bounds for TEMPLATE-SEARCH.

Datasets

Not discussed in the paper. The paper deals with theoretical properties of sequences and algorithms, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Surprising Behavior of Non-Monotone Patterns: The paper reveals that some non-monotone patterns are surprisingly hard to test, requiring significantly more queries than simple monotone patterns, even if their structural difference is small.
  • Structure is Key: The complexity of testing is not just about the length of the pattern but its specific internal structure. The USPN quantifies this structural hardness.
  • Adaptivity Matters (A Lot): The hierarchy of adaptivity for the (1,3,2) pattern shows that even a small amount of adaptivity can lead to substantial query savings, highlighting the power of adaptive algorithms in property testing.
  • Tightness of Bounds: The paper achieves bounds that are often tight up to polylogarithmic factors, suggesting a near-complete understanding of the query complexity for many scenarios.

Key Results

  • Improved Non-Adaptive Bounds: For most permutations of length $k$, non-adaptive one-sided tests require $\tilde{O}(\epsilon^{-1/(k-\Theta(1))}) n^{1-1/(k-\Theta(1))}$ queries. For the hardest permutations, this is $\tilde{O}(\epsilon^{-1/(k-1)}) n^{1-1/(k-1)}$.
  • Permutation-Dependent Lower Bound: A general lower bound is established based on the USPN of a permutation, $\tilde{\Omega}(\epsilon^{-1/u(\pi)}) n^{1-1/u(\pi)}$, which is conjectured to be tight.
  • Adaptivity Hierarchy for (1,3,2): For the (1,3,2) pattern, an $r$-round adaptive test can achieve query complexity of $\tilde{O}(\epsilon^{-1}) n^{1-1/(2r+O(1))}$, showing a significant improvement over non-adaptive tests. Conversely, $r$-round tests are shown to require $\tilde{\Omega}(n^{1/2+1/(2r+O(1))})$ queries.

Limitations and Future Work

  • Adaptive Case for General Permutations: While the paper makes progress on adaptivity for a specific pattern, the question of whether all permutations can be tested adaptively with polylogarithmic queries remains open.
  • Two-Sided Testing: Most results are for one-sided tests. Understanding the complexity of two-sided tests, especially for non-monotone patterns, is an open area.
  • Families of Patterns: The paper focuses on single forbidden patterns. Extending the understanding to testing for families of patterns is a direction for future research.
  • Multi-dimensional Structures: The behavior of $\pi$-freeness in higher-dimensional structures (hypergrids, hypercubes) is still not fully understood.

Summary updated

Abstract

A sequence f: {1, …, n} → R contains a permutation π of length k if there exist i1 < · · · < ik such that, for all x, y, f (ix) < f (iy) if and only if π(x) < π(y); otherwise, f is said to be π-free. In this work, we consider the problem of testing for π-freeness with one-sided error, continuing the investigation of [Newman et al., SODA’17]. We demonstrate a surprising behavior for non-adaptive tests with one-sided error: While a trivial sampling-based approach yields an ε-test for π-freeness making Θ(ε–1/kn1–1/k) queries, our lower bounds imply that this is almost optimal for most permutations! Specifically, for most permutations π of length k, any non-adaptive one-sided ε-test requires ε–1/(k–Θ(1))n1–1/(k–Θ(1)) queries; furthermore, the permutations that are hardest to test require Θ(ε–1/(k–1)n1–1/(k–1)) queries, which is tight in n and ε. Additionally, we show two hierarchical behaviors here. First, for any k and l ≤ k – 1, there exists some π of length k that requires non-adaptive queries. Second, we show an adaptivity hierarchy for π = (1, 3, 2) by proving upper and lower bounds for (one- and two-sided) testing of π-freeness with r rounds of adaptivity. The results answer open questions of Newman et al. and [Canonne and Gur, CCC’17].
BibTeX
@inproceedings{beneliezer2018improved,
  author = {Omri Ben-Eliezer and Clément L. Canonne},
  title = {{Improved Bounds for Testing Forbidden Order Patterns}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.137},
}
Figure