Polynomial-Time Mistake-Bounded Language Generation

The authors introduce a faster (polynomial-time) approach to a method for learning languages by making mistakes, originally proposed by Kleinberg, Peale, and Reingold. They show that specific types of Boolean functions, like parities of variables and conjunctions of literals, can be learned efficiently using this method. Their main finding is that all monotone Boolean functions with a limited number of maxterms can also be learned in polynomial time, which includes functions computable by polynomial-size decision trees. They explain their technique using a new game involving writing numbers on a board, making the approach more understandable.