Polynomial-Time Mistake-Bounded Language Generation
For computational learning theorists, this work extends the MBLG framework to polynomial-time settings, providing new positive results for several function families.
The paper introduces a polynomial-time version of the mistake-bounded language generation (MBLG) framework and shows that families like parities, conjunctions, and monotone Boolean functions with polynomially-many maxterms are polynomial-time MBLG. The latter includes all monotone Boolean functions computable by polynomial-size decision trees.
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.