Electronic Journal Article
@Article
Zeitschriftenartikel in einem eJournal 

BibTeX cite key*: 
ASS12 

Title*: 
Quasipolynomial Hittingset for SetdepthDelta Formulas 

Note: 

(LaTeX) Abstract: 
We call a depth$4$ formula $C$ {\em setdepth$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{setdepth$\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 bottommost $\Pi$layer are allowed to compute arbitrary monomials.
In this work, we give a hittingset generator for setdepth$\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 setdepth$\D$ formula. In other words, we give a {\em quasi}polynomial time \emph{blackbox} polynomial identity test for such constantdepth formulas. Previously, the very special case of $\D=3$ (also known as {\em setmultilinear} depth$3$ circuits) had no known subexponential time hittingset generator. This was declared as an open problem by Shpilka \& Yehudayoff (FnTTCS 2010); the model being first studied by Nisan \& Wigderson (FOCS 1995) and recently by Forbes \& Shpilka (STOC 2012 \& ECCC TR12115). 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$(\D1)$ formulas over a {\em Hadamard algebra}, after applying a `shift' on the variables. We propose a new algebraic conjecture about the \emph{lowsupport rankconcentration} in the latter formulas, and manage to prove it in the case of setdepth$\D$ formulas. 
URL for the Abstract: 

Categories / Keywords: 

HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Internal 

MPG Unit:  MaxPlanckInstitut 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 = {Quasipolynomial Hittingset for SetdepthDelta Formulas},
JOURNAL = {arXiv},
PUBLISHER = {Cornell University Library},
YEAR = {2012},
VOLUME = {abs/1209.2333},
PAGES = {113},
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 