# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Quasi-polynomial Hitting-set for Set-depth-delta Formulas

##### Locator

http://arxiv.org/abs/1209.2333

(Any fulltext)

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Agrawal, M., Saha, C., & Saxena, N. (2012). Quasi-polynomial Hitting-set for Set-depth-delta
Formulas.* arXiv,* *abs/1209.2333*, 1-13.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-C4AD-1

##### Abstract

We call a depth-4 formula C \em set-depth-4} if there exists a (unknown)
partition X_1\sqcup⋅s\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 Σ and \Pi
gates, with a Σ-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)^{ Δ -
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 ε\log s / \log \log s, for a fixed constant ε <
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.