Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-022 | 14th February 2011 15:36

Algebraic Independence and Blackbox Identity Testing



Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal number $r$ of algebraically independent polynomials in the set. In this paper we design blackbox and efficient linear maps $\varphi$ that reduce the number of variables from $n$ to $r$ but maintain $\mbox{trdeg}\{\varphi(f_i)\}_i = r$, assuming $f_i$'s sparse and small $r$. We apply these fundamental maps to solve several cases of blackbox identity testing:

(1) Given a polynomial-degree circuit $C$ and sparse polynomials $f_1,\ldots, f_m$ with trdeg $r$, we can test blackbox $D := C(f_1, \ldots, f_m)$ for zeroness in $\mbox{poly}(\mbox{size}(D))^r$ time.
(2) Define a $\Sigma\Pi\Sigma\Pi_\delta(k,s,n)$ circuit $C$ to be of the form $\sum_{i=1}^k \prod_{j=1}^s f_{i,j}$, where $f_{i,j}$ are sparse $n$-variate polynomials of degree at most $\delta$. For $k = 2$ we give a $\mbox{poly}(\delta sn)^{\delta^2}$ time blackbox identity test.
(3) For a general depth-$4$ circuit we define a notion of rank. Assuming there is a rank bound $R$ for minimal simple $\Sigma\Pi\Sigma\Pi_\delta(k,s,n)$ identities, we give a $\mbox{poly}(\delta snR)^{Rk\delta^2}$ time blackbox identity test for $\Sigma\Pi\Sigma\Pi_\delta(k,s,n)$ circuits. This partially generalizes the state of the art of depth-$3$ to depth-$4$ circuits.

The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.

ISSN 1433-8092 | Imprint