Electronic Journal Article @Article Zeitschriftenartikel in einem e-Journal

 Show entries of: this year (2021) | last year (2020) | two years ago (2019) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Saha, Chandan Saptharishi, Ramprasad Saxena, Nitin dblp dblp dblp Not MPG Author(s): Saptharishi, Ramprasad Saxena, Nitin
 BibTeX cite key*: SSS12

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

 Journal

 Publisher
 Publisher's Name: Birkhäuser Publisher's URL: Publisher's Address: Basel ISSN: 1420-8954

 Vol, No, Year, pp.
 Volume: 22 Number: 1 Month: Year*: 2013 Pages: 39-69 Number of VG Pages: Sequence Number: DOI: 10.1007/s00037-012-0054-4

 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 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). URL for the Abstract: Categories / Keywords: Chinese remaindering, circuits, depth-3, depth-4, factorization, Galois rings, ideal theory, identity testing HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@MISC{SSS12,
AUTHOR = {Saha, Chandan and Saptharishi, Ramprasad and Saxena, Nitin},
TITLE = {A Case of Depth-3 Identity Testing, Sparse Factorization and Duality},
JOURNAL = {Computational Complexity},
PUBLISHER = {Birkhäuser},
YEAR = {2013},
NUMBER = {1},
VOLUME = {22},
PAGES = {39--69},