論文の概要: Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem

• arxiv url: http://arxiv.org/abs/2010.12629v1
• Date: Fri, 23 Oct 2020 19:21:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-27 22:34:28.971588
• Title: Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
• Title（参考訳）: フアンの感度理論のデグリー対近似デグリーと量子的含意
• Authors: Scott Aaronson and Shalev Ben-David and Robin Kothari and Shravas Rao and Avishay Tal
• Abstract要約: すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
• 参考スコア（独自算出の注目度）: 4.549831511476248
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $\bullet \quad \mathrm{deg}(f) = O(\widetilde{\mathrm{deg}}(f)^2)$: The degree of $f$ is at most quadratic in the approximate degree of $f$. This is optimal as witnessed by the OR function. $\bullet \quad \mathrm{D}(f) = O(\mathrm{Q}(f)^4)$: The deterministic query complexity of $f$ is at most quartic in the quantum query complexity of $f$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $\mathrm{Q}(f)=\Omega(n)$, which is also optimal. We also show that the approximate degree of any read-once formula on $n$ variables is $\Theta(\sqrt{n})$.
• Abstract（参考訳）: huang (2019) の最近のブレークスルーに基づき、任意のブール関数 $f$ に対し、$\bullet \quad \mathrm{deg}(f) = o(\widetilde{\mathrm{deg}}(f)^2)$:$f$ の次数は、ほぼ$f$ の次数で最大二次である。 これはOR関数で見られるように最適である。 $\bullet \quad \mathrm{d}(f) = o(\mathrm{q}(f)^4)$: $f$の決定論的クエリの複雑さは、量子クエリの複雑性である$f$の最大四分法である。 ambainis, balodis, belovs, lee, santha, smotrovs (2017) による既知の分離 (ログファクタ) と一致している。 これらの結果を適用して、Aanderaa--Karp--Rosenberg予想の量子アナログを解く。 f$ がその隣接行列によって指定された$n$-vertex グラフの非自明な単調グラフの性質であるなら、$\mathrm{q}(f)=\omega(n)$ もまた最適である。 また、$n$変数上の任意の読み取りオンス公式の近似次数は$\Theta(\sqrt{n})$であることを示す。

関連論文リスト

• 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)
• 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)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。 我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
  論文  参考訳（メタデータ） (2021-11-01T20:45:42Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Quantum Implications of Huang's Sensitivity Theorem [4.970364068620607]
  ブール関数の総和が$f$の場合、決定論的クエリ複雑性である$D(f)$は、量子的クエリ複雑性において少なくとも準位であることを示す。 また、Aanderaa-Karp-Rosenberg予想の量子アナログを解くためにもこの結果を利用する。
  論文  参考訳（メタデータ） (2020-04-28T00:54:23Z)
• The quantum query complexity of composition with a relation [78.55044112903148]
  Belovs は負の重み付け逆法の修正版 $mathrmADV_relpm(f)$ を与えた。 関係が効率よく検証できる:$mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$。
  論文  参考訳（メタデータ） (2020-04-14T12:07:20Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。