Fugu-MT 論文翻訳(概要): A Collapsible Polynomial Hierarchy for Promise Problems

論文の概要: A Collapsible Polynomial Hierarchy for Promise Problems

arxiv url: http://arxiv.org/abs/2311.12228v1
Date: Mon, 20 Nov 2023 22:56:26 GMT
ステータス: 処理完了
システム内更新日: 2023-11-23 02:44:29.793045
Title: A Collapsible Polynomial Hierarchy for Promise Problems
Title（参考訳）: 公約問題に対する可算多項式階層
Authors: Chirag Falor, Shu Ge and Anand Natarajan
Abstract要約: 我々は、階層に関する一般的な結果を、問題を約束するために拡張された階層のバージョンに一般化する。本稿では,公約問題のクラスに対する存在的および普遍的作用素の新たな定義を提案する。
参考スコア（独自算出の注目度）: 0.6144680854063939
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The polynomial hierarchy has been widely studied in classical complexity theory. In this paper, we will generalize some commonly known results about the polynomial hierarchy to a version of the hierarchy extended to promise problems. This paper proposes new definitions of existential and universal operators for classes of promise problems. Applying these to BQP, we recover the hierarchy proposed by Gharibian et al. (MFCS 2018). Moreover, using our definition, we give an easy proof of the collapse of this hierarchy under a Karp-Lipton-like scenario, which was an open question for the original definition of Gharibian et al.
Abstract（参考訳）: 多項式階層は古典的複雑性理論において広く研究されている。本稿では,多項式階層についてよく知られた結果を,promise問題に拡張された階層のバージョンに一般化する。本稿では,promise問題のクラスに対する存在および普遍作用素の新しい定義を提案する。これらをBQPに適用し、Gharibianらによって提案された階層を復元する(MFCS 2018)。さらに、我々の定義を用いて、この階層がカルプ・リプトンのようなシナリオの下で崩壊するという簡単な証明を与える。

関連論文リスト

The Complexity of Algebraic Algorithms for LWE [0.0]
我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
論文参考訳（メタデータ） (2024-02-12T17:59:26Z)
Solving Degree Bounds For Iterated Polynomial Systems [0.0]
我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
論文参考訳（メタデータ） (2023-10-05T16:10:14Z)
Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
ヘテロジニアス知識統合のための質問分解手法を提案する。階層的質問分解木(RoHT)を用いた新しい2段階XQAフレームワークを提案する。複雑なQAデータセットKQA ProとMusiqueの実験は、我々のフレームワークがSOTAメソッドを著しく上回っていることを示している。
論文参考訳（メタデータ） (2023-05-24T11:45:59Z)
State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
本稿では,非可換変数の状態とそれらの積の形式状態を紹介する。これは、すべての正の状態と正の状態が、分母を持つ正方形の和であることを示している。また、Avinetengle Kritivsatzが状態設定で保持できないことも確認されている。
論文参考訳（メタデータ） (2023-01-29T18:52:21Z)
Multi-Task Off-Policy Learning from Bandit Feedback [54.96011624223482]
本稿では,階層型非政治最適化アルゴリズム (HierOPO) を提案する。学習方針の準最適性にタスクごとのバウンダリを証明し、階層モデルを使用しないよりも明確な改善を示す。我々の理論的および実証的な結果は、各タスクを個別に解くよりも、階層を使うことの明確な利点を示している。
論文参考訳（メタデータ） (2022-12-09T08:26:27Z)
Deep Hierarchy in Bandits [51.22833900944146]
行動の報酬は、しばしば相関する。統計的効率を最大化するためには,これらの相関を学習に活用することが重要である。平均作用報酬の相関が階層的ベイズモデルで表されるこの問題のバンディット変法を定式化する。
論文参考訳（メタデータ） (2022-02-03T08:15:53Z)
General stabilizer approach for constructing highly entangled graph states [0.0]
k-ユニフォーム (kUNI) や絶対最大エンタングルド (AME) 状態のような高絡み合いの多粒子状態は、量子ネットワークやその他の量子情報アプリケーションにおいて重要な資源となる。ここでは、既知のk-UNIおよびAME状態のクラスを、古典的誤り訂正符号とquditグラフ状態を組み合わせた、そのような状態を明示的に構築する手法を導入することにより、大幅に拡張する。
論文参考訳（メタデータ） (2021-11-15T19:06:57Z)
Hierarchical Bayesian Bandits [51.67132887113412]
このクラスでは,任意の問題に適用可能な自然階層型トンプソンサンプリングアルゴリズム (hierTS) を解析する。私たちの後悔の限界は、タスクが順次あるいは並列に解決された場合を含む、そのような問題の多くの事例に当てはまる。実験により、階層構造はタスク間の知識共有に役立つことが示された。
論文参考訳（メタデータ） (2021-11-12T20:33:09Z)
Orthogonalizing Convolutional Layers with the Cayley Transform [83.73855414030646]
直交に制約された畳み込み層をパラメータ化するための代替手法を提案し,評価する。本手法は,大規模畳み込みにおいても直交性が高次に保たれることを示す。
論文参考訳（メタデータ） (2021-04-14T23:54:55Z)
Hierarchical Poset Decoding for Compositional Generalization in Language [52.13611501363484]
出力が部分的に順序付けられた集合(命題)である構造化予測タスクとして人間の言語理解を形式化する。現在のエンコーダ・デコーダアーキテクチャは意味論のポーズ構造を適切に考慮していない。本稿では,言語における合成一般化のための新しい階層型ポーズデコーディングパラダイムを提案する。
論文参考訳（メタデータ） (2020-10-15T14:34:26Z)
Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文参考訳（メタデータ） (2020-01-13T13:16:13Z)

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