Item

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.