Note: 

(LaTeX) Abstract: 
Polynomial identity testing (PIT) problem is known to be challenging even
for constant depth arithmetic circuits. 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 \emph{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 \emph{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 an
affine linear polynomial and $b$ is a constant. We give a deterministic
polynomial time test, along with the computation of \emph{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 \emph{dual}
representation. The dual representation of polynomials (Saxena, ICALP
2008) is a technique to express a productofsums of univariates as a
sumofproducts of univariates. We generalize this technique by
combining it with a generalized Chinese remaindering to solve these
two problems (over any field). 
URL for the Abstract: 

Categories / Keywords: 
Chinese remaindering, circuits, depth3, depth4, factorization, Galois rings, ideal theory, identity testing 
HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Internal 
