Blackbox Polynomial Identity Testing for Depth 3 Circuits
Blackbox Polynomial Identity Testing for Depth 3 Circuits
复制标题
深度 3 电路的黑盒多项式恒等测试
DOI：
10.1109/focs.2009.67
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Shubhangi Saraf
中科院分区：
文献类型：
--
作者：
N. Kayal;Shubhangi Saraf
我们研究深度三个算术电路，并具有界面的顶部风扇。我们为深度的第一个确定性多项式时间黑框身份测试进行了三个电路，并在理性数字领域具有有界的顶部粉丝，从而解决了克里瓦斯和斯皮尔曼提出的问题（STOC 2001）。我们的主要技术结果是用于深度三个电路的结构定理，该电路具有有界的顶部风扇，可计算零多项式。特别是我们表明，如果具有真实系数的电路C很简单，最小化并计算零多项式，则C的等级可以仅由顶部Fanin的函数界定。这证明了DVIR和Shpilka的猜想的弱形式（Stoc 2005）在三个算术电路的深度相同深度的结构上。我们的BlackBox身份测试从该结构定理结合使用Karnin和Shpilka（CCC 2008）。我们对结构定理的证明利用了R^n中有限点的几何形状。我们确定在电路C中出现的线性形式，其中r^n中的点。然后，我们展示如何应用Sylvester的高维版本 - Gallai定理（来自发病率几何学定理），以识别出现在C中的特殊线性形式，以便在线性形式消失的子空间上，C限制了更简单的。电路计算零多项式。这使我们能够构建一个有限制电路等级的归纳论点。尽管以前已经暗示了此类定理从发病率几何形状中的实用性，但我们的证明是第一个完全发展连接并有效利用它的证明。
We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is a structural theorem for depth three circuits with bounded top fanin that compute the zero polynomial. In particular we show that if a circuit C with real coefficients is simple, minimal and computes the zero polynomial, then the rank of C can be upper bounded by a function only of the top fanin. This proves a weak form of a conjecture of Dvir and Shpilka (STOC 2005) on the structure of identically zero depth three arithmetic circuits. Our blackbox identity test follows from this structural theorem by combining it with a construction of Karnin and Shpilka (CCC 2008). Our proof of the structure theorem exploits the geometry of finite point sets in R^n. We identify the linear forms appearing in the circuit C with points in R^n. We then show how to apply high dimensional versions of the Sylvester--Gallai Theorem, a theorem from incidence-geometry, to identify a special linear form appearing in C, such that on the subspace where the linear form vanishes, C restricts to a simpler circuit computing the zero polynomial. This allows us to build an inductive argument bounding the rank of our circuit. While the utility of such theorems from incidence geometry for identity testing has been hinted at before, our proof is the first to develop the connection fully and utilize it effectively.