論文の概要: A Tight Composition Theorem for the Randomized Query Complexity of
Partial Functions
- arxiv url: http://arxiv.org/abs/2002.10809v2
- Date: Mon, 7 Dec 2020 09:52:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 00:07:09.941052
- Title: A Tight Composition Theorem for the Randomized Query Complexity of
Partial Functions
- Title（参考訳）: 部分関数のランダム化クエリ複雑性に対するタイトな合成定理
- Authors: Shalev Ben-David, Eric Blais
- Abstract要約: 合成関数のランダム化クエリ複雑性に関する2つの新しい結果を示す。
すべての$f$と$g$に対して、$(Rcirc g)=Omega(mathopnoisyR(f)cdot R(g))$, ここで$mathopnoisyR(f)$は、ノイズ入力に対する$f$の計算コストを表す尺度である。
- 参考スコア（独自算出の注目度）: 1.2284934135116514
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove two new results about the randomized query complexity of composed
functions. First, we show that the randomized composition conjecture is false:
there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ
g)\ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially
smaller than the right hand side (though in our construction, both sides are
polylogarithmic in the input size of $f$).
Second, we show that for all $f$ and $g$, $R(f\circ
g)=\Omega(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{noisyR}(f)$ is a
measure describing the cost of computing $f$ on noisy oracle inputs. We show
that this composition theorem is the strongest possible of its type: for any
measure $M(\cdot)$ satisfying $R(f\circ g)=\Omega(M(f)R(g))$ for all $f$ and
$g$, it must hold that $\mathop{noisyR}(f)=\Omega(M(f))$ for all $f$. We also
give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies
$\mathop{noisyR}(f)=\Theta(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the
input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$
bits.
- Abstract（参考訳）: 合成関数のランダム化クエリ複雑性に関する2つの新しい結果を示す。
まず、ランダム化合成予想は偽であることを示す: $r(f\circ) となる部分ブール関数 $f$ と $g$ の族が存在する。
g)\ll r である。
(f)R
(g)$。
実際、左辺は右辺よりも多項式的に小さくすることができる(我々の構成では、両方の辺は入力サイズが$f$の多対数である)。
次に、すべての$f$と$g$に対して$R(f\circ)を示す。
g)=\Omega(\mathop{noisyR}
(f)\cdot R
(g))$, ここで$\mathop{noisyr}
(f)$は、雑音の多いオラクル入力に対する$f$の計算コストを表す尺度である。
任意の測度$M(\cdot)$に対して$R(f\circ)を満たす。
g)=\Omega(M)
(f)R
(g))$ すべての$f$ と $g$ に対して、$\mathop{noisyr} を保持する必要がある。
(f)=\omega(m)
(f))すべての$f$に対して$です。
また、測度 $\mathop{noisyR} のクリーンな特徴づけを与える。
(f)$:$\mathop{noisyr}を満たす
(f)=\Theta(R(f\circ gapmaj_n)/R(gapmaj_n))$, ここで$n$は$f$の入力サイズであり、$gapmaj_n$は$n$上の$\sqrt{n}$-gap多数関数である。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Randomised Composition and Small-Bias Minimax [0.9252523881586053]
クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。
まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
論文 参考訳（メタデータ） (2022-08-26T23:32:19Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z) - A Canonical Transform for Strengthening the Local $L^p$-Type Universal
Approximation Property [4.18804572788063]
任意の機械学習モデルクラス $mathscrFsubseteq C(mathbbRd,mathbbRD)$ が $Lp_mu(mathbbRd,mathbbRD)$ で密であることを保証する。
本稿では、「$mathscrF$'s approximation property」という正準変換を導入することにより、この近似理論問題に対する一般的な解を提案する。
論文 参考訳（メタデータ） (2020-06-24T17:46:35Z) - Robust testing of low-dimensional functions [8.927163098772589]
著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。
耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)バージョンを実証する。
クエリ複雑性が$kO(mathsfpoly(log k/epsilon))$,$k$-halfspacesの交叉のクラスに対して完全耐雑音試験器を得る。
論文 参考訳（メタデータ） (2020-04-24T10:23:12Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。