ECCC-Report TR11-021https://eccc.weizmann.ac.il/report/2011/021Comments and Revisions published for TR11-021en-usMon, 14 Feb 2011 03:40:39 +0200
Paper TR11-021
| A Case of Depth-3 Identity Testing, Sparse Factorization and Duality |
Chandan Saha,
Ramprasad Saptharishi,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2011/021Finding 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).
Mon, 14 Feb 2011 03:40:39 +0200https://eccc.weizmann.ac.il/report/2011/021