Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

Journal Title*:

Computational Complexity

Journal's URL:

http://link.springer.com/journal/37

Download URL
for the article:

http://link.springer.com/content/pdf/10.1007%2Fs00037-012-0054-4

Language:

English

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

Abstract, Links, (C)

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},
ADDRESS = {Basel},
ISBN = {1420-8954},
DOI = {10.1007/s00037-012-0054-4},
}


Entry last modified by Stephanie Müller, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/17/2013 08:31:38 AM
Revisions
3.
2.
1.
0.
Editor(s)
Stephanie Müller
Anja Becker
Chandan Saha
Chandan Saha
Edit Dates
15.01.2014 14:14:29
08.02.2013 12:05:32
01/18/2013 05:18:31 AM
01/17/2013 08:31:38 AM