Fugu-MT 論文翻訳(概要): Enumeration Classes Defined by Circuits

論文の概要: Enumeration Classes Defined by Circuits

arxiv url: http://arxiv.org/abs/2205.00539v1
Date: Sun, 1 May 2022 19:02:03 GMT
ステータス: 処理完了
システム内更新日: 2022-05-04 01:58:25.989521
Title: Enumeration Classes Defined by Circuits
Title（参考訳）: 回路で定義した列挙クラス
Authors: Nadia Creignou, Arnaud Durand and Heribert Vollmer
Abstract要約: グラフ理論、グレイコード列挙、命題充足性からよく知られた列挙問題を見つける。我々は$mathbfDelayP$で知られている様々な問題の複雑さを区別するフレームワークを得る。
参考スコア（独自算出の注目度）: 0.5161531917413706
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in $\mathbf{DelayP}$, for which a formal way of comparison was not possible to this day.
Abstract（参考訳）: 我々は,ブール回路を列挙器として用いることで定義される非常に低いクラスを導入することで,列挙問題の複雑性の景観を洗練する。グラフ理論、グレイ符号列挙法、クラスにおける命題満足度など、よく知られた列挙問題を見つける。このようにして、"\mathbf{delayp}$"で知られている様々な問題の複雑さを区別するためのフレームワークを得る。

関連論文リスト

Sequence graphs realizations and ambiguity in language models [1.4732811715354455]
計算的観点から,シーケンスグラフの実現可能性とあいまいさについて検討する。大きさが 3 の窓に対して、w が定数であるとしても、すべての不変量の硬さを証明する。本稿では、実現可能性問題を解く整数プログラムと、列挙問題の解法を動的プログラミングで結論付ける。
論文参考訳（メタデータ） (2024-02-13T22:22:51Z)
Understanding and Mitigating Classification Errors Through Interpretable Token Patterns [58.91023283103762]
容易に解釈可能な用語でエラーを特徴付けることは、分類器が体系的なエラーを起こす傾向にあるかどうかを洞察する。正しい予測と誤予測を区別するトークンのパターンを発見することを提案する。提案手法であるPremiseが実際によく動作することを示す。
論文参考訳（メタデータ） (2023-11-18T00:24:26Z)
Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文参考訳（メタデータ） (2023-10-05T07:10:40Z)
On the Complexity of Computing G\"odel Numbers [0.0]
計算可能なすべての列の問題を研究し、Wehrauchの複雑性を分類する。分類のベンチマークとして、閉かつコンパクトな選択問題とそれらの自然数へのジャンプを用いる。これらの問題は、逆数学におけるカービー・パリ階層から知られているように、帰納法と有界性原理に対応している。
論文参考訳（メタデータ） (2023-02-08T17:31:20Z)
On the Complexity of Representation Learning in Contextual Linear Bandits [110.84649234726442]
表現学習は線形帯域よりも根本的に複雑であることを示す。特に、与えられた表現の集合で学ぶことは、その集合の中で最悪の実現可能な表現で学ぶことよりも決して単純ではない。
論文参考訳（メタデータ） (2022-12-19T13:08:58Z)
Component twin-width as a parameter for BINARY-CSP and its semiring generalisations [6.671201304858938]
二項制約満足度問題(Binary-CSPs)のいくつかの一般化の細粒度およびパラメータ化複雑性について検討する。我々の出発点は、これらの問題に対して複雑さの上界をもたらすいくつかのアルゴリズム的アプローチが共通の構造を共有することである。したがって、BINary-CSP の異なる一般化を統一する半環に依存する代数的アプローチを探求する。
論文参考訳（メタデータ） (2022-07-14T22:04:48Z)
Consistent circuits for indefinite causal order [0.0]
論理的に一貫性があるが、循環因果構造を特徴とする多くの量子過程が提案されている。ここでは,エキゾチックな因果構造を持つプロセスを構築する方法を提案する。因果不等式に反するプロセスを含む、エキゾチックなプロセスの標準的な例が、このような方法で生成可能なプロセスのクラスであることを示す。
論文参考訳（メタデータ） (2022-06-20T23:15:52Z)
Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文参考訳（メタデータ） (2022-02-08T16:39:57Z)
Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文参考訳（メタデータ） (2021-05-21T22:22:02Z)
Differentiable Inductive Logic Programming for Structured Examples [6.8774606688738995]
雑音や構造化例から論理プログラムを学ぶための新しいフレームワークを提案する。我々の新しいフレームワークは、シーケンスやツリーなど、ノイズや構造化された例から論理プログラムを学習できることを示します。我々のフレームワークは、関数記号を持つ複数の節からなる複雑なプログラムを扱うためにスケールできる。
論文参考訳（メタデータ） (2021-03-02T13:47:33Z)
An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文参考訳（メタデータ） (2020-06-18T20:09:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。