cs.CC · 2606.16077 Copy arXiv ID · Jun 15, 2026 Save Polynomial-Time Mistake-Bounded Language Generation Authors: Héctor Jimenez , Alexander Kozachinskiy , Vicente Opazo
Organizations: University of Chile · CENIA
Abstract In this note, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We observe that the family of parities of variables, and the family of conjunctions of literals, are polynomial-time MBLG. Our main result states that the family of monotone Boolean functions with polynomially-many maxterms is polynomial-time MBLG. This family includes all monotone Boolean functions, computable by polynomial-size decision trees. Our technique can be presented as a new combinatorial game about writing numbers on a board.
Explore similar work May 11, 2026 · Jon Kleinberg, Charlotte Peale, Omer Reingold X-Logsmask
Jun 24, 2026 · Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2 Context-Free Grammars Data Generation
May 28, 2026 · Jon Kleinberg, Anay Mehrotra, Amin Saberi +1 Infinite-Width Gaussian Limit Worst-Case
May 11, 2026 · cs.LG J/K move · Enter open · S save
Jon Kleinberg, Charlotte Peale, Omer Reingold
We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "mistake-bounded generation." While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al. (2025), enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of
C d i m ( L ) \mathsf{Cdim}(L) Cdim ( L ) and a mistake bound of
⌊ log 2 ∣ L ∣ ⌋ \lfloor \log_2 |L| \rfloor ⌊ log 2 ∣ L ∣ ⌋ , whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes
O ( log i ) O(\log i) O ( log i ) necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary's suboptimality.