論文の概要: Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

• arxiv url: http://arxiv.org/abs/2609.05153v1
• Date: Fri, 04 Sep 2026 13:55:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-07 18:15:24.063125
• Title: Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$
• Title（参考訳）: $\mathsf{QAC}^0$における対称ブール関数のファンアウト複素性
• Authors: Boyan Xu, Lvzhou Li,
• Abstract要約: 計算$mathttPARITY_n$は$mathttFANOUT_(f)$ under $mathsfQAC0$ reducesを実装することと等価である。 ここでは、真に遷移半径$(f)$であることを示す: computing $f$ and implementation $mathttFANOUT_(f)$ is equivalent under $mathsfQAC0$ reductions。
• 参考スコア（独自算出の注目度）: 7.883691246794115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? We show that the answer is exactly the transition radius $ρ(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{ρ(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $ρ(f)\ge n^δ$ for some constant $δ>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+Ω(1)}$ must be nonsymmetric.
• Abstract（参考訳）: $\mathsf{QAC}^0$が$\mathtt{PARITY}_n$を計算できるかどうかは未定である。 計算$\mathtt{PARITY}_n$は$\mathtt{FANOUT}_n$を$\mathsf{QAC}^0$で実装するのと同じである。 任意の対称ブール関数 $f:\{0,1\}^n\to\{0,1\}$ に対して、どんなファンアウトサイズが必要で、$f$ in $\mathsf{QAC}^0$ の計算に十分か? 計算は$f$で、実装は$\mathtt{FANOUT}_{ρ(f)}$は$\mathsf{QAC}^0$で等価である。 特に、ある定数 $δ>0$ に対して $ρ(f)\ge n^δ$ ならば、計算 $f$ は $\mathsf{QAC}^0_{\mathrm{f}}$-complete である。 パトリの定理と組み合わせると、我々の特徴づけは、$\matht{PARITY}_n \notin \mathsf{QAC}^0$ ならば、近似次数 $n^{1/2+Ω(1)}$ の任意のブール函数は非対称でなければならないことを意味する。

関連論文リスト

• Hardness Amplification for (Sparse) LPN [5.1105538244022135]
  雑音を学習するパリティ(mathsfLPN$)とそのスパース変種に対する新しい硬度増幅結果を示す。 で$mathsfLPN$を解くアルゴリズムは、"ほとんどすべてのインスタンス"で$mathsfLPN$を解くアルゴリズムに変換することができる。 同じ増幅アプローチを$mathsfLPN$ over $mathbbF_q$とSparse-$mathsfLPN$に拡張します。
  論文  参考訳（メタデータ） (2026-05-11T06:34:37Z)
• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。 我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
  論文  参考訳（メタデータ） (2026-01-06T18:40:44Z)
• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。 以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
  論文  参考訳（メタデータ） (2026-01-06T18:34:07Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• 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)
• Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
  ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。 我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
  論文  参考訳（メタデータ） (2023-09-07T19:37:52Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)

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

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