Polynomial-Time Mistake-Bounded Language Generation
Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo
cs.CC cs.LG
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.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.