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 Goto entry point

 Author, Editor
 Author(s): Agrawal, Manindra Saha, Chandan Saxena, Nitin dblp dblp dblp Not MPG Author(s): Agrawal, Manindra Saxena, Nitin
 BibTeX cite key*: ASS12

 Title
 Title*: Quasi-polynomial Hitting-set for Set-depth-Delta Formulas

 Journal
 Journal Title*: arXiv Journal's URL: Download URL for the article: http://arxiv.org/abs/1209.2333 Language: English

 Publisher
 Publisher's Name: Cornell University Library Publisher's URL: Publisher's Address: Ithaca, NY ISSN:

 Vol, No, Year, pp.
 Volume: abs/1209.2333 Number: Month: Year*: 2012 Pages: 1-13 Number of VG Pages: Sequence Number: DOI:

 Note: (LaTeX) Abstract: We call a depth-$4$ formula $C$ {\em set-depth-$4$} if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e.~$C(\term{x})=\sum_{i=1}^k \prod_{j=1}^{d}$ $f_{i,j}(\term{x}_{X_j})$, where $f_{i,j}$ is a {\em sparse} polynomial in $\F[\term{x}_{X_j}]$. Extending this definition to any depth - we call a depth-$\D$ formula $C$ (consisting of alternating layers of $\Sigma$ and $\Pi$ gates, with a $\Sigma$-gate on top) a \emph{set-depth-$\D$} formula if every $\Pi$-layer in $C$ respects a (unknown) partition on the variables; if $\D$ is even then the product gates of the bottom-most $\Pi$-layer are allowed to compute arbitrary monomials. In this work, we give a hitting-set generator for set-depth-$\D$ formulas (over \emph{any} field) with running time polynomial in $\exp((\D^2\log s)^{ \Delta - 1})$, where $s$ is the size bound on the input set-depth-$\D$ formula. In other words, we give a {\em quasi}-polynomial time \emph{blackbox} polynomial identity test for such constant-depth formulas. Previously, the very special case of $\D=3$ (also known as {\em set-multilinear} depth-$3$ circuits) had no known sub-exponential time hitting-set generator. This was declared as an open problem by Shpilka \& Yehudayoff (FnT-TCS 2010); the model being first studied by Nisan \& Wigderson (FOCS 1995) and recently by Forbes \& Shpilka (STOC 2012 \& ECCC TR12-115). Our work settles this question, not only for depth-$3$ but, up to depth $\epsilon\log s / \log \log s$, for a fixed constant $\epsilon < 1$. The technique is to investigate depth-$\D$ formulas via depth-$(\D-1)$ formulas over a {\em Hadamard algebra}, after applying a `shift' on the variables. We propose a new algebraic conjecture about the \emph{low-support rank-concentration} in the latter formulas, and manage to prove it in the case of set-depth-$\D$ formulas. URL for the Abstract: Categories / Keywords: 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{ASS12,
AUTHOR = {Agrawal, Manindra and Saha, Chandan and Saxena, Nitin},
TITLE = {Quasi-polynomial Hitting-set for Set-depth-Delta Formulas},
JOURNAL = {arXiv},
PUBLISHER = {Cornell University Library},
YEAR = {2012},
VOLUME = {abs/1209.2333},
PAGES = {1--13},
ADDRESS = {Ithaca, NY},
}

Entry last modified by Anja Becker, 02/08/2013
Edit History (please click the blue arrow to see the details)

 Editor(s) [Library] Created 01/17/2013 08:50:32 AM Revisions 8. 7. 6. 5. 4. Editor(s) Anja Becker Anja Becker Anja Becker Anja Becker Anja Becker Edit Dates 08.02.2013 10:35:44 08.02.2013 10:34:55 08.02.2013 10:33:48 08.02.2013 10:33:38 08.02.2013 10:32:05