論文の概要: The General Adversary Bound: A Survey
- arxiv url: http://arxiv.org/abs/2104.06380v1
- Date: Tue, 13 Apr 2021 17:35:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-04-03 23:33:26.044724
- Title: The General Adversary Bound: A Survey
- Title(参考訳): The General Adversary Bound: A Survey
- Authors: Lily Li, Morgan Shirley
- Abstract要約: ベン・ライハルト(Ben Reichardt)は一連の結果において、関数の一般逆境界がその量子クエリの複雑さを特徴づけることを示した。
この調査は、証明を理解するのに必要な背景と定義をまとめたものだ。
- 参考スコア(独自算出の注目度): 2.3986080077861787
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Ben Reichardt showed in a series of results that the general adversary bound
of a function characterizes its quantum query complexity. This survey seeks to
aggregate the background and definitions necessary to understand the proof.
Notable among these are the lower bound proof, span programs, witness size, and
semi-definite programs. These definitions, in addition to examples and detailed
expositions, serve to give the reader a better intuition of the graph-theoretic
nature of the upper bound. We also include an applications of this result to
lower bounds on DeMorgan formula size.
- Abstract(参考訳): ベン・ライハルト(Ben Reichardt)は、関数の一般逆境界がその量子クエリの複雑さを特徴づけることを示した。
この調査は、証明を理解するために必要な背景と定義をまとめたものだ。
中でも注目すべきは、下限証明、スパンプログラム、証人サイズ、半定義プログラムである。
これらの定義は、例や詳細な表現に加えて、読者に上界のグラフ理論的な性質をより直感的に理解させるのに役立つ。
また、この結果をDeMorgan式のサイズの低い値に適用する。
関連論文リスト
- Layer Cake Representations for Quantum Divergences [8.397730500554047]
古典的発散の適切な量子拡張を定義するための新しい手法を提案する。
結果の量子 R'enyi と $f$-divergences は、積分表現によって最近定義されたものと同値であることが証明される。
論文 参考訳(メタデータ) (2025-07-09T17:27:34Z) - CLATTER: Comprehensive Entailment Reasoning for Hallucination Detection [60.98964268961243]
我々は,系統的かつ包括的な推論プロセスを実行するためのモデルを導くことで,モデルがよりきめ細やかで正確な絞り込み決定を実行できることを提案する。
我々は,(i)クレームの分解,(ii)サブクレームの属性と包含分類,および(iii)集約分類から成る3段階の推論プロセスを定義し,そのような導出推論が実際に幻覚検出の改善をもたらすことを示す。
論文 参考訳(メタデータ) (2025-06-05T17:02:52Z) - Hallucination Detection in LLMs with Topological Divergence on Attention Graphs [64.74977204942199]
幻覚(Halucination)、すなわち、事実的に誤ったコンテンツを生成することは、大きな言語モデルにとって重要な課題である。
本稿では,TOHA (Topology-based HAllucination detector) をRAG設定に導入する。
論文 参考訳(メタデータ) (2025-04-14T10:06:27Z) - A Compositional Atlas for Algebraic Circuits [35.95450187283255]
クエリの大規模なクラスは、半環上の基本演算子(アグリゲーション、製品、および要素ワイドマッピング)の組み合わせに対応することを示す。
分析を応用して、このような多くの合成クエリに対して、新しいトラクタビリティ条件を導出する。
論文 参考訳(メタデータ) (2024-12-07T00:51:46Z) - Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds [14.183849746284816]
多様体仮説は、自然の高次元データが低次元多様体の周辺で支えられていることを言う。
統計的および学習に基づく手法の最近の成功は、この仮説を実証的に支持している。
我々は、一般化特性に直接関係する理論的な統計的複雑さの結果を提供する。
論文 参考訳(メタデータ) (2024-08-13T15:56:42Z) - Proving Theorems Recursively [80.42431358105482]
本稿では、定理をレベル・バイ・レベルで証明するPOETRYを提案する。
従来のステップバイステップメソッドとは異なり、POETRYは各レベルで証明のスケッチを検索する。
また,POETRYが検出した最大証明長は10~26。
論文 参考訳(メタデータ) (2024-05-23T10:35:08Z) - Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
我々は、よりきめ細かいアプローチを論じ、対象パターンの基底''にすべての構造の準同型数を含む。
これにより計算複雑性の面で追加のオーバーヘッドを発生させずに、より表現力のあるアーキテクチャが得られる。
論文 参考訳(メタデータ) (2024-02-13T16:57:06Z) - Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
ユークリッド空間における集合の被覆数について上限を証明する。
ここでは、イムディン・コントによる最もよく知られた一般境界が改善されることが示される。
本稿では,3つの計算応用における結果のパワーについて説明する。
論文 参考訳(メタデータ) (2023-11-09T03:06:59Z) - Universal coding, intrinsic volumes, and metric complexity [3.4265828682659705]
この代入では、ゴールは、約$mathbbRnの平均値部分集合を持つ最良の分布と同様に、実数値観測の列を予測、または同等に予測することである。
解析の一環として、一般制約集合に対するミニマックス冗長性も特徴付ける。
情報理論の古典的な結果と対比する。
論文 参考訳(メタデータ) (2023-03-13T16:54:04Z) - Large deviations rates for stochastic gradient descent with strongly
convex functions [11.247580943940916]
勾配降下を伴う一般高確率境界の研究のための公式な枠組みを提供する。
強い凸関数を持つSGDの上限となる大きな偏差が見つかる。
論文 参考訳(メタデータ) (2022-11-02T09:15:26Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳(メタデータ) (2021-10-12T02:21:30Z) - Finding Good Proofs for Description Logic Entailments Using Recursive
Quality Measures (Extended Technical Report) [15.150938933215906]
証明がいかに理解可能であるかは、使用する計算量だけでなく、特定の証明の性質にも依存する。
我々は、計算と測度の幅広いクラスを対象とする一般的な結果を目指す。
論文 参考訳(メタデータ) (2021-04-27T12:34:13Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳(メタデータ) (2020-11-04T10:25:13Z) - Relative Deviation Margin Bounds [55.22251993239944]
我々はRademacher複雑性の観点から、分布依存と一般家庭に有効な2種類の学習境界を与える。
有限モーメントの仮定の下で、非有界な損失関数に対する分布依存的一般化境界を導出する。
論文 参考訳(メタデータ) (2020-06-26T12:37:17Z) - Lower bounds in multiple testing: A framework based on derandomized
proxies [107.69746750639584]
本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。
これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
論文 参考訳(メタデータ) (2020-05-07T19:59:51Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳(メタデータ) (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。