Fugu-MT 論文翻訳(概要): The General Adversary Bound: A Survey

論文の概要: 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式のサイズの低い値に適用する。

関連論文リスト

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)
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)

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