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 |
|
Edit History (please click the blue arrow to see the details)