We call a depth-$4$ formula $C$ $\textit{ 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(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call a depth-$\Delta$ formula $C$ (consisting of alternating layers of $\Sigma$ and $\Pi$ gates, with a $\Sigma$-gate on top) a $\textit{set-depth-}\Delta$ formula if every $\Pi$-layer in $C$ respects a (unknown) partition on the variables; if $\Delta$ 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-$\Delta$ formulas (over $\textit{any}$ field) with running time polynomial in $\exp(({\Delta}^2\log s)^{ \Delta - 1})$, where $s$ is the size bound on the input set-depth-$\Delta$ formula. In other words, we give a $\textit{quasi}$-polynomial time $\textit{blackbox}$ polynomial identity test for such constant-depth formulas. Previously, the very special case of $\Delta=3$ (also known as $\textit{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 $\epsilon\log s / \log \log s$ $ $for a fixed constant $\epsilon < 1$.

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