論文の概要: A General Composition Theorem for Approximate Degree

• arxiv url: http://arxiv.org/abs/2609.30139v1
• Date: Thu, 24 Sep 2026 17:08:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:10.142056
• Title: A General Composition Theorem for Approximate Degree
• Title（参考訳）: 近似Degreeの一般的な構成理論
• Abstract要約: すべての Boolean 関数に対して $f:0,1nto0,1$, [ widetildedeg(fcirc g) =!left( widetildedeg(f),widetildedeg(g) ] ここで $widetildedeg$ は定数エラー近似度を表す。
• 参考スコア（独自算出の注目度）: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree.
• Abstract（参考訳）: ブール関数複雑性における長年の開問題は、近似次数がブロック合成の下で乗法的に構成するかどうかを問うものである。 一般の乗法上界が知られているが、それと一致する下界は、関数の制限クラスに対してのみ確立されている。 すべてのブール関数に対するこの問題は、一致する下界を証明することによって解決する。 シェルストフの上界と共に、我々の結果は、全ブール関数のすべての対に対して、$f:\{0,1\}^n\to\{0,1\}$および$g:\{0,1\}^m\to\{0,1\}$, \[\widetilde{deg}(f\circ] が成り立つことを示している。 g) = ー\! \left( \widetilde{deg}) (f)\,\widetilde{deg} (g) \right) \] where $\widetilde{deg}$は定数エラー近似度を表す。

関連論文リスト

• On the Approximate Non-Deterministic Degree of Total Boolean Functions [0.2864713389096699]
  関数 $f$, $mathsfndeg_(f)$ (書式 $mathsfN_(f)$ for brevity) 30年以上にわたって開かれた合理的次数予想は、最近Kothari、KovacsDeak、Wang、Yangによって解決された。
  論文  参考訳（メタデータ） (2026-05-22T07:52:09Z)
• Quantum Search With Generalized Wildcards [0.4310167974376404]
  我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。 以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
  論文  参考訳（メタデータ） (2025-11-06T18:55:05Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• 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 low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees Defining a Partial Boolean Function [13.713089043895959]
  一対のブール関数 $f, g colon 0,1J to 0,1$ で定義される部分ブール関数を考えると、$f cdot g = 0$ であり、$f$ と $g$ は可分正規形式または二分決定木で定義される。
  論文  参考訳（メタデータ） (2021-02-09T08:46:50Z)
• 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)
• 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)

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

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