论文标题
多项式程度结合了非刚性矩阵和小线性电路的方程式
A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits
论文作者
论文摘要
我们表明，对于（zariski闭合）非辅助矩阵的（zariski封闭），最多只有$ \ mathsf {poly}（n）$的定义方程式：也就是说，我们证明，对于每个大型字段$ \ mathbb {f} $ 1}，\ ldots，x_ {n，n，n}] $ of Leg的$，最多是$ \ mathsf {poly}（n）$，使每个矩阵$ m $ y $最多可以写成$ n/100 $的矩阵总和，最多可将$ n/100 $的矩阵和矩阵矩阵和矩阵矩阵矩阵和矩阵矩阵，最多$ n^2/100 $满足$ p（m）$ p（m）$ p（m）= 0 $ p（m）= 0 $。这证实了Gesmundo，Hauenstein，Ikenmeyer和Landsberg [GHIL16]的猜想，并改善了此问题已知的最佳上限，从$ \ exp（n^2）$ [KLPS14，GHIL16]到$ \ \ \ \ m athsf {poly}（n）$。 我们还显示了所有矩阵$ m $的（Zariski封闭）集合的多项式学位，以便可以由$ m $表示的线性转换由代数电路计算，最多最多$ n^2/200 $边缘（无限制限制深度）。据我们所知，当电路的深度不受限制时，在这项工作之前，没有任何界限。 我们的方法是基本和简短的，并且依赖于Shpilka和Volkovich [SV15]的多项式图来构建低度“通用”地图，以用于非刚性矩阵和小线性电路。将这种结构与简单的维度计数参数结合在一起，以表明任何此类多项式图都具有低度歼灭多项式的均可完成证明。 作为推论，我们表明多项式身份测试问题的任何衍生化都将暗示新的电路下限。 Kabanets和Impagliazzo证明了类似（但无与伦比的）定理[KI04]。
We show that there is a defining equation of degree at most $\mathsf{poly}(n)$ for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}[x_{1, 1}, \ldots, x_{n, n}]$ of degree at most $\mathsf{poly}(n)$ such that every matrix $M$ which can be written as a sum of a matrix of rank at most $n/100$ and a matrix of sparsity at most $n^2/100$ satisfies $P(M) = 0$. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16] and improves the best upper bound known for this problem down from $\exp(n^2)$ [KLPS14, GHIL16] to $\mathsf{poly}(n)$. We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices $M$ such that the linear transformation represented by $M$ can be computed by an algebraic circuit with at most $n^2/200$ edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [SV15] to construct low degree "universal" maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [KI04].
