論文の概要: Polynomial-Time Mistake-Bounded Language Generation
- arxiv url: http://arxiv.org/abs/2606.16077v1
- Date: Mon, 15 Jun 2026 00:31:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-16 16:21:34.022792
- Title: Polynomial-Time Mistake-Bounded Language Generation
- Title（参考訳）: 多項式時間誤り境界言語生成
- Authors: Héctor Jimenez, Alexander Kozachinskiy, Vicente Opazo,
- Abstract要約: Kleinberg, Peale, Reingold によるミスバウンド言語生成(MBLG)フレームワークの a26 時間版を紹介した。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 本稿では,Kleinberg, Peale, Reingold (2026) によるミスバウンド言語生成(MBLG)フレームワークの多項式時間版を紹介する。
変数のパリティの族とリテラルの結合の族は多項式時間MBLGであることが観察された。
本研究の主な成果は,多項式時間MBLGの最大値を持つ単調ブール関数の族が,多項式時間MBLGであることである。
この族は多項式サイズの決定木で計算可能なすべての単調ブール函数を含む。
本手法は,ボード上に数字を書くための新たな組み合わせゲームとして提示できる。
関連論文リスト
- Ensembling Language Models with Sequential Monte Carlo [48.149136054981334]
我々は、$K$の言語モデルを$f$のアンサンブル分布に構成するための統一的なフレームワークを導入する。
より優れた後部近似により、より優れたアンサンブル性能が得られることを示す。
論文 参考訳（メタデータ） (2026-03-05T17:54:31Z) - Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects [0.6554326244334868]
多変量体のツリー幅は、ハイパーグラフのツリー幅であり、その項に対応するハイパーエッジを持つ。
有界木幅の符号としてのブール関数の表現はしきい値表現と呼ばれる。
論文 参考訳（メタデータ） (2025-01-14T18:28:08Z) - Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
Weak Connectedness PolynomialsとStrong Connectedness Polynomialsを1次論理文に使用する。
既存の公理の全てを抽出可能であることが知られているWFOMCを解くのに使用できる。
論文 参考訳（メタデータ） (2024-07-16T16:01:25Z) - On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
二進体 $mathbbF$ 上の極大族を特徴づける。
我々の発見は、よりオープンないくつかの質問を呼び起こし、この研究の拡張バージョンで対処する予定です。
論文 参考訳（メタデータ） (2024-05-14T16:30:28Z) - Unambiguity and Fewness for Nonuniform Families of Polynomial-Size
Nondeterministic Finite Automata [0.0]
非決定論的有限オートマトンは、最大で "one" (曖昧) 、"polynomially many" (fw) の受け入れパス、あるいは各固定された構成につながる計算/関数パスを持つ。
我々はこれらの変種が計算力において互いに異なるという証明が得られていない仮定で証明する。
論文 参考訳（メタデータ） (2023-11-16T15:52:24Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。
主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。
2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
論文 参考訳（メタデータ） (2021-07-14T07:23:46Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。