論文の概要: Efficient reconstruction of depth three circuits with top fan-in two
- arxiv url: http://arxiv.org/abs/2103.07445v1
- Date: Fri, 12 Mar 2021 18:19:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-15 14:35:57.893246
- Title: Efficient reconstruction of depth three circuits with top fan-in two
- Title（参考訳）: トップファンイン2を用いた深度3回路の高効率再構成
- Authors: Gaurav Sinha
- Abstract要約: 有限体上のブラックボックス再構成問題を解くための効率的なランダム化アルゴリズムを開発した。
この回路クラスの最初のブラックボックス再構成アルゴリズムは、$log |mathbbF|$で実行されます。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop efficient randomized algorithms to solve the black-box
reconstruction problem for polynomials over finite fields, computable by depth
three arithmetic circuits with alternating addition/multiplication gates, such
that output gate is an addition gate with in-degree two. These circuits compute
polynomials of form $G\times(T_1 + T_2)$, where $G,T_1,T_2$ are product of
affine forms, and polynomials $T_1,T_2$ have no common factors. Rank of such a
circuit is defined as dimension of vector space spanned by all affine factors
of $T_1$ and $T_2$. For any polynomial $f$ computable by such a circuit,
$rank(f)$ is defined to be the minimum rank of any such circuit computing it.
Our work develops randomized reconstruction algorithms which take as input
black-box access to a polynomial $f$ (over finite field $\mathbb{F}$),
computable by such a circuit. Here are the results.
1 [Low rank]: When $5\leq rank(f) = O(\log^3 d)$, it runs in time
$(nd^{\log^3d}\log |\mathbb{F}|)^{O(1)}$, and, with high probability, outputs a
depth three circuit computing $f$, with top addition gate having in-degree
$\leq d^{rank(f)}$.
2 [High rank]: When $rank(f) = \Omega(\log^3 d)$, it runs in time $(nd\log
|\mathbb{F}|)^{O(1)}$, and, with high probability, outputs a depth three
circuit computing $f$, with top addition gate having in-degree two.
Ours is the first blackbox reconstruction algorithm for this circuit class,
that runs in time polynomial in $\log |\mathbb{F}|$. This problem has been
mentioned as an open problem in [GKL12] (STOC 2012)
- Abstract（参考訳）: 我々は,有限体上の多項式のブラックボックス再構成問題を,入出力ゲートが2次加算ゲートであるような加算/乗算ゲートを交互に有する深さ3個の演算回路で計算できる効率的なランダム化アルゴリズムを開発した。
これらの回路は $G\times(T_1 + T_2)$ の多項式を計算し、$G,T_1,T_2$ はアフィン形式の積であり、多項式 $T_1,T_2$ は共通の因子を持たない。
このような回路のランクは、$T_1$ と $T_2$ のすべてのアフィン因子によってまたがるベクトル空間の次元として定義される。
そのような回路で計算可能な多項式 $f$ に対して、$rank(f)$ はそのような回路の最小ランクとして定義される。
このような回路で計算可能な多項式$f$(有限フィールド$\mathbb{F}$)への入力ブラックボックスアクセスを行うランダム化再構成アルゴリズムを開発した。
以下は結果です。
1 [低ランク]: 5\leq rank(f) = o(\log^3d)$ の場合、時刻 $(nd^{\log^3d}\log |\mathbb{f}|)^{o(1)}$ で動作し、高い確率で深さ 3 の回路を f$ で計算し、最上位の加算ゲートは $\leq d^{rank(f)}$ となる。
2 [high rank]: $rank(f) = \omega(\log^3 d)$ の場合、時刻$(nd\log |\mathbb{f}|)^{o(1)}$ で動作し、高い確率で深さ3の回路をf$で計算し、最上位の加算ゲートは2度である。
この回路クラスに対する最初のブラックボックス再構成アルゴリズムであり、$\log |\mathbb{F}|$ の時間多項式で実行される。
この問題は[GKL12](STOC 2012)のオープンな問題として言及されています。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。
また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文 参考訳（メタデータ） (2024-11-01T19:04:13Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。
これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
論文 参考訳（メタデータ） (2024-10-09T02:55:57Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳（メタデータ） (2023-11-16T07:25:06Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - 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) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳（メタデータ） (2020-04-15T06:18:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。