Near-Optimal Property Testers for Pattern Matching

Ce Jin, Adam Polak2025 · DOI

TL;DR

This paper introduces near-optimal algorithms for property testing of exact pattern matching. They achieve optimal time and query complexities across various scenarios, including a novel separation between adaptive and non-adaptive approaches for the $n=m+o(m)$ case. This work significantly advances the state-of-the-art in efficiently verifying string matching properties.

What Problem Does This Paper Address?

The core problem is property testing for exact pattern matching. Given a pattern $P$ and a text $T$, we want to know if $P$ appears as a substring in $T$. Property testing relaxes this by asking if $P$ occurs exactly or if it's "far" from any substring of $T$ in terms of Hamming distance (specifically, if its Hamming distance to every substring of $T$ of the same length is greater than a threshold $k$). The challenge is to do this efficiently, ideally in sublinear time and with few queries to the input strings, especially for very large texts and patterns. Existing sublinear algorithms had limitations, particularly in the $n=m+o(m)$ regime and in achieving optimal query complexity.

Methods

The paper presents both adaptive and non-adaptive property testers.

  • Non-adaptive testers: These build upon previous work ([CGK+20]) by employing a structured sampling approach based on p-periodic sampling and Karp-Rabin fingerprints. A key innovation is a novel combinatorial lemma (Lemma 2.2) that characterizes mismatches in a way that allows for more efficient sampling and analysis, particularly for low-Hamming-weight scenarios. They also introduce a technique to handle general inputs by finding "good" subsets of positions.
  • Adaptive testers: These leverage the non-adaptive testers and a more sophisticated analysis involving potential functions and probabilistic arguments. They use a "good block" finding strategy and a technique to iteratively eliminate candidate occurrences.
  • Lower bounds: The authors establish unconditional lower bounds using Yao's principle, constructing "hard" input distributions (Planted vs. Random, Equal vs. Independent) to prove that their algorithms are indeed optimal up to polylogarithmic factors.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Optimal Complexity Achieved: The paper demonstrates that near-optimal time and query complexities, matching lower bounds, are achievable for property testing of exact pattern matching across various parameter regimes.
  • Adaptive vs. Non-Adaptive Separation: A significant finding is the demonstration of a separation between adaptive and non-adaptive algorithms in the $n=m+o(m)$ regime, where adaptive algorithms offer better performance.
  • Novel Combinatorial Characterization: A new lemma (Lemma 2.2) provides a powerful way to characterize mismatches, which is crucial for both their adaptive and non-adaptive algorithms. This lemma shows that a small number of selected positions can cover a significant portion of mismatches.
  • Handling Low-Hamming-Weight Cases: The techniques are effective even for low-Hamming-weight inputs, which are often considered "hard" instances.

Key Results

  • Non-adaptive tester: Achieves $\widetilde{\mathcal{O}}(n/\sqrt{k})$ time for $n=m+\Theta(m)$ and $\widetilde{\mathcal{O}}(\sqrt{nm/k} + n/k)$ for $n=m+\Omega(m)$.
  • Adaptive tester: Achieves $\widetilde{\mathcal{O}}(\sqrt{m(n-m+1)/k} + n/k)$ time.
  • Adaptive vs. Non-adaptive Separation: For $n=m+o(m)$, adaptive algorithms are strictly better than non-adaptive ones.
  • Lower Bounds: Unconditional lower bounds match the complexities of their algorithms, proving optimality.
  • Tolerant Testing: The algorithms can be extended to handle tolerant property testing (distinguishing between $k'$ and $k$ mismatches) with small overheads.

Limitations and Future Work

  • Tolerant Testing Gap: While their algorithms handle tolerant testing, the gap $k/k'$ they can distinguish is limited (around 2). Improving this for smaller gaps (e.g., $1+\epsilon$) remains an open question, especially for adaptive testers.
  • Generalizing Adaptive Algorithms: The authors note that generalizing their adaptive algorithm to the tolerant and reporting versions is an open problem.
  • $n=m+o(m)$ for Tolerant Testing: The time complexity for tolerant testing in the $n=m+o(m)$ regime is still an open question.
  • $k$-Mismatch Problem Optimization: Optimizing the time complexity for computing $Occ_k(P,T)$ (the $k$-mismatch problem) for $n=m+o(m)$ is also suggested as future work.

Summary updated

Abstract

The classic exact pattern matching problem, given two strings——a pattern P of length m and a text T of length n—— asks whether P occurs as a substring of T, that is, $P= T[i. . i+m)$ holds for some $i \in[0. . n-m]$. A property tester for the problem needs to distinguish (with high probability) the following two cases for some threshold $k \in[1. . m)$: the Yes case, where P occurs as a substring of T, and the No case, where $\boldsymbol{P}$ has Hamming distance greater than k from every substring of T, that is, P has no k-mismatch occurrence in T. In this work, we provide adaptive and non-adaptive property testers for the exact pattern matching problem, jointly covering the whole spectrum of parameters. We further establish unconditional lower bounds demonstrating that the time and query complexities of our algorithms are optimal, up to polylog n factors hidden within the $\widetilde{\mathcal{O}}(\cdot)$ notation below. In the most studied regime of $n=m+\Theta(m)$, our nonadaptive property tester has the time complexity of $\widetilde{\mathcal{O}}(n / \sqrt{k})$, and a matching lower bound remains valid for the query complexity of adaptive algorithms. This improves both upon a folklore solution that attains the optimal query complexity but requires $\Omega(n)$ time, and upon the only previously known sublineartime property tester, by Chan, Golan, Kociumaka, Kopelowitz, and Porat [STOC 2020], with time complexity $\widetilde{\mathcal{O}}(n / \sqrt[3]{k})$. The aforementioned results remain valid for $n=m+\Omega(m)$, where our optimal running time $\widetilde{\mathcal{O}}(\sqrt{n m / k}+n / k)$ improves upon the previously best time complexity of $\mathcal{O}\left(\sqrt[3]{n^{2} m / k}+n / k\right)$. In the regime of $n=m+o(m)$, which has not been targeted in any previous work, we establish a surprising separation between adaptive and non-adaptive algorithms, whose optimal time and query complexities are $\widetilde{\mathcal{O}}(\sqrt{(n-m+1) m / k}+n / k)$ and $\widetilde{\mathcal{O}}(\min (n \sqrt{n-m+1} / k, \sqrt{n m / k}+n / k))$, respectively. Our non-adaptive algorithms answer Yes with high probability not only when P has an exact occurrence in T but also when P has an occurrence with at most $k^{\prime}=\Omega(k / \log n)$ mismatches. The gap $k / k^{\prime}$ can be reduced by slightly increasing the running time; an arbitrarily small polynomial overhead already suffices to achieve a constant gap. Moreover, upon request, our algorithms may output a set $A \subseteq[0. . n-m]$ that contains the starting positions of all $\boldsymbol{k}^{\prime}$-mismatch occurrences of $\boldsymbol{P}$ in $\boldsymbol{T}$ and no starting position of an occurrence with more than k mismatches. The key technical innovation behind all our property testers is a novel characterization of the mismatches between the pattern P and the fragments $T[i . . i+m)$ across $i \in[0. . n-m]$. We show that one can select $\widetilde{\mathcal{O}}(k \cdot n / m)$ positions within P and T so that, for every $i \in[0. . n-m]$, at least $\min \left(k, k_{i}\right)$ of the $k_{i}$ mismatches between P and $T[i .. i+m)$ involve a selected position. Previously, such a construction was known for k
BibTeX
@misc{jin2025near,
  author = {Ce Jin and Adam Polak},
  title = {{Near-Optimal Property Testers for Pattern Matching}},
  year = {2025},
  doi = {10.1109/focs63196.2025.00086},
}
Figure