Mulmuley and Sohoni (2001) proposed an ambitious program, called the
Geometric Complexity Theory
(GCT), to prove P ≠ NP and related conjectures using algebraic geometry and representation theory. Gradually, GCT has introduced new structures and questions in complexity theory. GCT tries to capture an algebraic/geometric notion of ‘approximation’ by defining the
border
classes. Surprisingly, (Kumar ToCT’20) proved the universal power of the border of top-fanin-2 depth-3 circuits (
\(\overline{({\Sigma ^{[2]}\Pi \Sigma }} \)
), which is in complete contrast to its classical model. Recently, (Dutta,Dwivedi,Saxena, FOCS’21) put an upper bound, by showing that bounded top-fanin border depth-3 circuits (
\(\overline{{\Sigma ^{[k]}\Pi \Sigma }} \)
for constant
k
) can be computed by polynomial-size algebraic branching programs (ABPs). It was left open to show an
exponential
separation between the class of ABPs and
\(\overline{{\Sigma ^{[k]}\Pi \Sigma }} \)
.
In this article, we show a strong exponential separation between any two consecutive border classes,
\(\overline{{\Sigma ^{[k]}\Pi \Sigma }} \)
and
\(\overline{{\Sigma ^{[k+1]}\Pi \Sigma }} \)
, thus establishing an
optimal hierarchy
of constant top-fanin border depth-3 circuits. In the language of GCT, we prove an exponential hierarchy for
padded
-
k
-th-secant-varieties of the Chow variety of
\(\mathbb {F}^{n+1} \)
. This positively answers [Open question 2 of Dutta,Dwivedi,Saxena FOCS’21] and [Problem 8.10 with constant
r
, of Landsberg, Annal.Ferrara’15].