# Polynomial-Time Mistake-Bounded Language Generation

arXiv: https://arxiv.org/abs/2606.16077 · HTML: https://mlsanity.com/paper/2606.16077/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Builds on (most cited first, 5 of 5)

- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [Language Generation: Complexity Barriers and Implications for Learning](https://mlsanity.com/paper/2511.05759/) (2025)
- [Mistake-Bounded Language Generation](https://mlsanity.com/paper/2605.10809/) (2026)

## Built on by (most cited first, 2 of 2)

- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)

## Abstract (arXiv)

In this paper, we introduce a polynomial-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold (2026). We obtain upper and lower bounds for a number of simple families of Boolean functions. Namely, we first observe that families of parities of variables, symmetric functions and 2CNFs are polynomial-time MBLG. We then show that the family of monotone functions with polynomially-many maxterms is polynomial-time MBLG. For instance, disjunctions of literals are monotone Boolean functions with 1 maxterms, and thus polynomial-time MBLG. Under the strong RSA assumption, we show that disjunctions of literals are not polynomial-time MBLG. From the latter result, we deduce that polynomial-time MBLG families are not closed under union, and that there are families that are polynomial-time PAC learnable but not polynomial-time MBLG (again, under the strong RSA assumption). Finally, assuming existence of injective one-way functions, we show that there are polynomial-time MBLG families that are not polynomial-time PAC learnable.