Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-021 | 13th February 2011 21:21

A Case of Depth-3 Identity Testing, Sparse Factorization and Duality


Authors: Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
Publication: 14th February 2011 03:40
Downloads: 2746


Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is a vast generalization of: verify whether a bounded top fanin depth-$3$ circuit equals a *sparse* polynomial (given as a sum of monomial terms). Formally, given a depth-$3$ circuit $C$, having constant many general product gates and arbitrarily many *semidiagonal* product gates, test if the output of $C$ is identically zero. A semidiagonal product gate in $C$ computes a product of the form $m \cdot \prod_{i=1}^{b}{\ell_i^{e_i}}$, where $m$ is a monomial, $\ell_i$ is a linear polynomial and $b$ is a constant. We give a deterministic polynomial time test, along with the computation of *leading* monomials of semidiagonal circuits over local rings.

The second problem is on verifying a given sparse polynomial factorization, which is a classical question (von zur Gathen, FOCS 1983): Given multivariate sparse polynomials $f, g_1,\ldots, g_t$ explicitly, check if $f = \prod_{i=1}^{t}{g_i}$. For the special case when every $g_i$ is a sum of univariate polynomials, we give a deterministic polynomial time test. We characterize the factors of such $g_i$'s and even show how to test the divisibility of $f$ by the powers of such polynomials.

The common tools used are Chinese remaindering and *dual* representation. The dual representation of polynomials (Saxena, ICALP 2008) is a technique to express a product-of-sums of univariates as a sum-of-products of univariates. We generalize this technique by combining it with a generalized Chinese remaindering to solve these two problems (over any field).

ISSN 1433-8092 | Imprint