Quality Control Algorithms for Pattern Counting

• URL: http://arxiv.org/abs/2608.03439v1
• Date: Tue, 04 Aug 2026 10:35:00 GMT
• Title: Quality Control Algorithms for Pattern Counting
• Abstract summary: Empirical algorithms have not exploited the asymmetry in the definition of quality control problems.<n>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.
• Score: 17.340766930817335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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$.

Related papers

• The Invisible Lottery: How Subtle Cues Steer Algorithm Choice in LLM Code Generation [0.6564588068252765]
  Incidental prompt cues, meaning contextual words or metadata outside the task specification, can steer which algorithm the model selects.<n>We define algorithm steering as cue-induced shifts in algorithm-family distributions.<n>Direct algorithm naming is the most reliable mitigation we tested.
  arXiv  Detail & Related papers  (2026-06-02T11:17:28Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  A generic online learning algorithm is developed for a class of ''monotone'' problems.<n>Our framework applies to several fundamental problems such as prophet inequality, Pandora's box, single-resource revenue management and posted pricing.
  arXiv  Detail & Related papers  (2023-12-24T07:46:37Z)
• Adversarially Robust Distributed Count Tracking via Partial Differential Privacy [17.43748116766233]
  We study the distributed tracking model, also known as distributed functional monitoring. This model involves $k$ sites each receiving a stream of items and communicating with the central server. For count tracking, it is known that there is a $sqrtk$ gap in communication between deterministic and randomized algorithms.
  arXiv  Detail & Related papers  (2023-11-01T07:42:13Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
  arXiv  Detail & Related papers  (2023-08-23T08:38:53Z)
• On the Existence of a Complexity in Fixed Budget Bandit Identification [0.0]
  In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. We show that there is no such complexity for several fixed budget identification tasks including Bernoulli best arm identification with two arms.
  arXiv  Detail & Related papers  (2023-03-16T16:39:00Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling. We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
  arXiv  Detail & Related papers  (2022-10-03T00:28:44Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits [27.09804256642197]
  We introduce a large family of algorithms inspired by the Frank-Wolfe algorithm. We construct new explicit algorithms for a broad class of problems. We explain this phenomenon on an insightful toy problem.
  arXiv  Detail & Related papers  (2021-10-18T09:36:36Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.