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):

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:


Abstract, Links, (C)

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
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: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