Polynomial-Time Mistake-Bounded Language Generation

• URL: http://arxiv.org/abs/2606.16077v1
• Date: Mon, 15 Jun 2026 00:31:11 GMT
• Title: Polynomial-Time Mistake-Bounded Language Generation
• Abstract summary: We introduce a26-time version of the mistake-bounded language generation (MBLG) framework due to Kleinberg, Peale, and Reingold.
• Score: 45.57297901648928
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• RecKAN: Kolmogorov-Arnold Networks with a Learnable Recursive Polynomial Basis [0.0]
  We introduce RecKAN, which defines the basis itself by a second order recurrence, $KAN_Rn+1(x) = (axbx+c) + (dxbx+c) + (dxn-1(x)$, whose five coefficients are learned.<n>We show that its degree grows linearly in $n$ exactly on the sub-family containing all of them, giving a concrete sense that learned basis can move beyond any fixed classical choice.
  arXiv  Detail & Related papers  (2026-09-01T18:01:32Z)
• The Complexity of Min-Max Optimization for Quadratic Polynomials [71.85811744604827]
  We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratics.<n>As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix.
  arXiv  Detail & Related papers  (2026-06-15T17:37:13Z)
• Ensembling Language Models with Sequential Monte Carlo [48.149136054981334]
  We introduce a unified framework for composing $K$ language models into $f$-ensemble distributions.<n>We show that better posterior approximations can yield better ensemble performance.
  arXiv  Detail & Related papers  (2026-03-05T17:54:31Z)
• Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects [0.6554326244334868]
  The tree-width of a multivariate is the tree-width of the hypergraph with hyperedges corresponding to its terms.<n>A representation of a Boolean function as the sign of a bounded tree-width is called a threshold representation.
  arXiv  Detail & Related papers  (2025-01-14T18:28:08Z)
• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  We use Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. We can use them to solve WFOMC with all of the existing axioms known to be tractable.
  arXiv  Detail & Related papers  (2024-07-16T16:01:25Z)
• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
  arXiv  Detail & Related papers  (2024-05-14T16:30:28Z)
• Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata [0.0]
  Nondeterministic finite automata have at most "one" (unambiguous), "polynomially many" (few) accepting paths, or computation/few paths leading to each fixed configuration. We prove with no unproven assumptions that some of these variants are different in computational power from each other.
  arXiv  Detail & Related papers  (2023-11-16T15:52:24Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Language learnability in the limit for general metrics: a Gold-Angluin result [91.3755431537592]
  We use Niyogi's extended version of a theorem by Blum and Blum (1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages in any given metric. When the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit.
  arXiv  Detail & Related papers  (2021-03-24T13:11:09Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.