Polynomial-Time Mistake-Bounded Language Generation

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.