Fugu-MT 論文翻訳(概要): Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation

論文の概要: Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation

arxiv url: http://arxiv.org/abs/2609.17578v1
Date: Fri, 28 Aug 2026 03:42:18 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-21 16:32:15.677758
Title: Generic Characteristic-Zero Equivalence Between Derivative Bézout Inversion and Multipoint Evaluation
Title（参考訳）: 導出ベズーインバージョンと多点評価の間のジェネリック特性-ゼロ等価性
Abstract要約: 固有正規化された Bezout 対 $s,t$ を $sZ+tZ'=1$ で満たし、$tm$ と $sm-1$ で計算する。古典的積木アプローチでは、$O(M_K(m)log m)$フィールド演算が必要であり、$M_K(m)$は、$K$に対して次数-$m$sを乗算するコストを表す。標数 0 の無限体上において、一般有理直線計画モデルにおいて、正準のすべての係数を計算することが証明される。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Let $a_1,\ldots,a_m$ be distinct elements of a field $K$, and let $Z(X)=\prod_{i=1}^m (X-a_i)$. We study the arithmetic complexity of computing the unique normalized Bezout pair $s,t$ satisfying $sZ+tZ'=1$, with $°t<m$ and $°s<m-1$. The classical product-tree approach requires $O(M_K(m)\log m)$ field operations, where $M_K(m)$ denotes the cost of multiplying degree-$<m$ polynomials over $K$. Thus, even when $M_K(m)=O(m\log m)$, the resulting bound is $O(m\log^2 m)$ rather than $O(m\log m)$. Over an infinite field of characteristic zero, we prove that, in the generic rational straight-line-program model, computing all coefficients of the canonical Bezout pair is equivalent, up to an additive $O(M_K(m))$ cost, to arbitrary-node multipoint polynomial evaluation and to interpolation. The main ingredient is an explicit differential reconstruction that recovers $Z$ from $(s,t)$ in $O(M_K(m))$ arithmetic operations on a nonempty Zariski-open subset. Combining this reconstruction with automatic differentiation and transposition yields the complexity equivalence. We further transfer Strassen's lower bound for the elementary symmetric functions to the Bezout problem, obtaining an $Ω(m\log m)$ nonscalar lower bound. Hence an $O(m\log m)$ algorithm, if it exists in this model, would be asymptotically optimal. The reconstruction is genuinely characteristic-dependent: in characteristic $p$, all squarefree polynomials $X^p+cX+d$, with fixed $c\ne 0$, have the same normalized Bezout pair $(0,c^{-1})$. Therefore the all-field, all-input $O(m\log m)$ problem remains open; generically in characteristic zero, however, it is reduced to the corresponding arbitrary-node multipoint evaluation and interpolation problem.
Abstract（参考訳）: a_1,\ldots,a_m$ を体 $K$ の別の元とし、$Z(X)=\prod_{i=1}^m (X-a_i)$ とする。我々は、一意に正規化されたベズー対 $s,t$ を $°t<m$ と $°s<m-1$ で満たす算術複雑性について研究する。古典的積木アプローチでは、$O(M_K(m)\log m)$場演算が必要であり、$M_K(m)$は次数-$<m$多項式を$K$に乗算するコストを表す。したがって、$M_K(m)=O(m\log m)$であっても、結果は$O(m\log^2 m)$であり、$O(m\log m)$である。典型的ベズー対のすべての係数は、任意のノード多重点多項式評価と補間に対する加算$O(M_K(m))$コストまで等価であることを示す。主な要素は、空でないザリスキ開部分集合上の$Z$を$(s,t)$ in$O(M_K(m))$算術演算から復元する明示的な微分再構成である。この再構成と自動微分と転位を組み合わせることで、複雑さの等価性が得られる。さらに、基本対称函数に対するストラッセンの下界をベズー問題に移し、$Ω(m\log m)$非スカラー下界を得る。したがって、$O(m\log m)$アルゴリズムは、もしこのモデルに存在するなら、漸近的に最適である。標数$p$では、すべての平方自由多項式$X^p+cX+d$、固定$c\ne 0$は、同じ正規化されたベズー対$(0,c^{-1})$を持つ。したがって、全フィールド、全入力 $O(m\log m)$ 問題は依然として開であり、一般に標数 0 で表されるが、対応する任意のノード多重点評価と補間問題に還元される。

関連論文リスト

Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
論文参考訳（メタデータ） (2026-04-27T10:23:24Z)
What Trace Powers Reveal About Log-Determinants: Closed-Form Estimators, Certificates, and Failure Modes [0.0]
トレースパワーへのアクセスを$p_k = tr(Ak)$, 行列パワーが利用可能であれば自然に研究する。非有界条件よりも連続的な正のモーメントが均一に正確であることはない。
論文参考訳（メタデータ） (2026-01-18T23:04:17Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文参考訳（メタデータ） (2024-03-14T15:04:45Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
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)
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)

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

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