We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition X1Xd of the variable indices [n] that the top product layer respects, i.e. C(x)=ki=1dj=1fij(xXj) where fij is a sparse polynomial in F[xXj]. Extending this definition to any depth - we call a depth- formula C (consisting of alternating layers of and gates, with a -gate on top) a set-depth- formula if every -layer in C respects a (unknown) partition on the variables; if is even then the product gates of the bottom-most -layer are allowed to compute arbitrary monomials.

In this work, we give a hitting-set generator for set-depth- formulas (over any field) with running time polynomial in exp((2logs)−1), where s is the size bound on the input set-depth- formula. In other words, we give a quasi-polynomial time blackbox polynomial identity test for such constant-depth formulas. Previously, the very special case of =3 (also known as 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). Our work settles this question, not only for depth-3 but, up to depth logsloglogs for a fixed constant 1.

The technique is to investigate depth- formulas via depth-(−1) formulas over a Hadamard algebra, after applying a `shift' on the variables. We propose a new algebraic conjecture about the low-support rank-concentration in the latter formulas, and manage to prove it in the case of set-depth- formulas.