{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaadelnmhntpeovr4qsjyuu2imfogye6unfocvmbhoeora6g6orn4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mof4gba6zev2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.16077v1",
  "publishedAt": "2026-06-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Héctor Jimenez",
    "Alexander Kozachinskiy",
    "Vicente Opazo"
  ],
  "textContent": "**Authors:** Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo\n\nIn 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.",
  "title": "Polynomial-Time Mistake-Bounded Language Generation"
}