hide
Free keywords:
-
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.
