Quality Control Algorithms for Pattern Counting

Cassandra Marcussen; Ronitt Rubinfeld; Madhu Sudan

cs.DSAug 4, 2026

Quality Control Algorithms for Pattern Counting

Authors: Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan

Abstract

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly $(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$ .

Explore similar work

May 28, 2026cs.FL

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated by a given pattern. Inclusion depth captures the mind-change complexity of pattern identification from positive data. The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma with at least two symbols, and whether it is computable in polynomial time. A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm. The problem connects pattern language inclusion, combinatorics on words, language identification in the limit, and mind-change-bounded learning.

Wei Luo

Computable Length Data Mining Probabilistic Inference Protein Language Model Universal

Ask PDF

Aug 3, 2026cs.DS

Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

We study the round complexity of learning a hidden partition

\mathcal{P}

of an

n

-element universe using PAIR queries: PAIR(

x,y

) tells us whether

x

and

y

belong to the same part of the partition or not. While it is easy to learn using

n|\mathcal{P}|

queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of

\mathcal{P}

is known. In particular they prove

Θ(\log\log n)

rounds are sufficient and necessary to limit the number of queries to

n|\mathcal{P}|

. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts

k = |\mathcal{P}|

is known, we give a simple 3-round randomized algorithm using

O(nk\log n)

queries with high probability, and prove that 2 rounds require

Ω(n^{4/3}k^{2/3})

queries -- the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using

O(n|\mathcal P|\log^2 n)

queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter,

Θ(\log n/\log\log n)

rounds are necessary and sufficient to obtain near-optimal query complexity.

Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic

Partitioning Sample Complexity Random

Ask PDF

Aug 2, 2026cs.DS

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as

n

grows, on the fraction of the first

n

elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that

1/2

is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of

1/2

with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to

1-1/e

. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.

Ziyi Cai, Shuangping Li, Yiheng Shen +2

Lower Bounds Generating Large Language Model Generation Length Finite

Ask PDF