論文の概要: Lower Bounding the AND-OR Tree via Symmetrization
- arxiv url: http://arxiv.org/abs/1907.06731v5
- Date: Wed, 22 Mar 2023 01:28:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 08:49:18.510773
- Title: Lower Bounding the AND-OR Tree via Symmetrization
- Title（参考訳）: 対称化によるAND-OR木の下界
- Authors: William Kretschmer
- Abstract要約: ここでは、$widetildemathrmdeg(mathsfAND_m circ mathsfOR_n) = widetildeOmega(sqrtmn)$を示す。
一連の対称性のステップを通して$mathsfOR$関数に還元することで、この下界を証明します。
- 参考スコア（独自算出の注目度）: 0.22843885788439797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a simple, nearly tight lower bound on the approximate degree of the
two-level $\mathsf{AND}$-$\mathsf{OR}$ tree using symmetrization arguments.
Specifically, we show that $\widetilde{\mathrm{deg}}(\mathsf{AND}_m \circ
\mathsf{OR}_n) = \widetilde{\Omega}(\sqrt{mn})$. We prove this lower bound via
reduction to the $\mathsf{OR}$ function through a series of symmetrization
steps, in contrast to most other proofs that involve formulating approximate
degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates
the power of a symmetrization technique involving Laurent polynomials
(polynomials with negative exponents) that was previously introduced by
Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].
- Abstract（参考訳）: シンメトリゼーションの引数を用いて、2レベル $\mathsf{AND}$-$\mathsf{OR}$ツリーの近似次数に対して、単純で、ほぼ厳密な下界を証明する。
具体的には、$\widetilde{\mathrm{deg}}(\mathsf{AND}_m \circ \mathsf{OR}_n) = \widetilde{\Omega}(\sqrt{mn})$を示す。
線形プログラムとして近似次数の定式化を含む他の証明(BT13, She13, BDBGK18]と対照的に、一連の対称性化ステップによる$\mathsf{OR}$関数への還元によるこの下界の証明を行う。
我々の証明はまた、Aaronson, Kothari, Kretschmer, Thaler [AKKT19] によって導入されたローラン多項式(負の指数を持つポリノミアル)を含む対称性化技術の力を示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Towards verifications of Krylov complexity [0.0]
私は16の量子力学系のモーメントの完全かつ明示的な表現をSchr"odinger と Heisenberg の両方で正確に解けるように提示する。
論文 参考訳（メタデータ） (2024-03-11T02:57:08Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Increasing subsequences, matrix loci, and Viennot shadows [0.0]
商 $mathbbF[mathbfx_n times n]/I_n$ が標準単項基底を持つことを示す。
また、 $mathbbF[mathbfx_n times n]/I_n$ を次数 $mathfrakS_n times MathfrakS_n$-module として計算する。
論文 参考訳（メタデータ） (2023-06-14T19:48:01Z) - Characterizing Kirkwood-Dirac nonclassicality and uncertainty diagram
based on discrete Fourier transform [6.344765041827868]
我々は、基底 $mathcal A$ から基底 $mathcal B$ への遷移行列である DFT 行列の不確かさ図に対して、穴がないことを示す。
DFT行列に基づく状態のKD非古典性は、支持不確実性関係を用いて完全に特徴付けることができる。
論文 参考訳（メタデータ） (2023-03-30T07:55:21Z) - 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) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Topological entanglement and hyperbolic volume [1.1909611351044664]
チャーン・サイモンズ理論は、還元密度行列の$m$-モーメントを3次元多様体の$Z(M_mathcalK_m)$として視覚化する設定を与える。
SU(2) 群に対して、$Z(M_mathcalK_m)$ は、おもに$k$ で成長できることを示す。
我々は、$ln Z(M_mathcalK_m)$が結び目の双曲体積$S3backslash mathcalK_mであると予想する。
論文 参考訳（メタデータ） (2021-06-07T07:51:03Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - A Positivstellensatz for Conditional SAGE Signomials [38.44747913332153]
条件付きSAGE証明書は$textitcomplete$であることを示す。
mathbbZ_+$の$pと特定の正定値関数$w(mathbfx)$は証明書によって検証される。
論文 参考訳（メタデータ） (2020-03-08T06:20:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。