Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-297 | 3rd November 2026 03:32

An Exponential Top Fan-In Hierarchy for Border Depth-4 Circuits

RSS-Feed




TR26-297
Authors: Anakin Dey, Pranjal Dutta, Zeyu Guo
Publication: 4th November 2026 07:47
Downloads: 13
Keywords: 


Abstract:

We study depth-$4$ algebraic circuits with bounded top and bottom fan-in over fields of characteristic $0$. These circuits compute sums of at most $k$ products of polynomials of degree at most $\delta$. We denote this class of circuits by $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$. Our hard polynomial for this class is $P_{k + 1,n}$, the sum of $k + 1$ monomials of degree $n$ on disjoint sets of variables. It can be computed by a depth-$3$ circuit of top fan-in $k + 1$ and size $O(kn)$.

We give an impossibility result showing that for all constants $k$ and $\delta$ and all sufficiently large $n$, no $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuit computes $P_{k + 1,n}$. For $k \geq 2$ and $\delta = 2$, this follows implicitly from the rank bound for $\Sigma^{[k]}\Pi\Sigma\Pi^{[2]}$ identities of Garg, Oliveira, Sengupta, Shalmon, and Shpilka (CCC 2026). To the best of our knowledge, this impossibility result was not known even for $k \geq 2$ and $\delta = 3$.

We also turn to border complexity, a notion central to geometric complexity theory, in which a polynomial only needs to be approximated arbitrarily well. Here impossibility fails over algebraically closed fields: Kumar (TOCT 2020) showed that $\overline{\Sigma^{[2]}\Pi\Sigma}$ circuits already approximate every polynomial, albeit with exponential size. In turn, we show that every $\overline{\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}}$ circuit computing $P_{k + 1,n}$ must have size $2^{\Omega(n)}$ when $k$ and $\delta$ are constants, in stark contrast to the exact depth-$3$ circuit of top fan-in $k + 1$ and size $O(kn)$. This lower bound gives an exponential top fan-in hierarchy for border depth-$4$ circuits of bounded bottom fan-in and answers the main open question of Dutta and Saxena (FOCS 2022, JACM 2026), who gave an analogous hierarchy for the case $\delta = 1$, i.e., depth $3$.

Along the way, we develop tools for border depth-$4$ circuits that apply to arbitrary polynomials and may have further applications.



ISSN 1433-8092 | Imprint