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-245 | 10th October 2026 20:25

Demystifying Border Depth-3 Circuits via Differential Equations

RSS-Feed

Abstract:

Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni in Geometric Complexity Theory (GCT), which is phrased in terms of border determinantal complexity. However, efficient debordering results are known only for a few restricted models.

In this paper, we study border depth-$3$ circuits of top fan-in $k$, denoted $\overline{\Sigma^{[k]}\Pi\Sigma}$. Dutta, Dwivedi, and Saxena (FOCS 2021) introduced a recursive technique called DiDIL and used it to show that every polynomial in the border of size-$s$ $\overline{\Sigma^{[k]}\Pi\Sigma}$ circuits has an algebraic branching program (ABP) of size $s^{\mathrm{exp}(k)}$, and that this border class has an explicit hitting set of size $s^{\mathrm{exp}(k)\cdot\log\log s}$. Building on DiDIL, Dutta and Saxena (JACM 2026) proved an exponential-gap top-fan-in hierarchy theorem, via a lower bound of the form $2^{\Omega(d/\mathrm{exp}(k))}$. In all three settings, the bounds depend exponentially on $k$.

We bypass DiDIL entirely, replacing it with a single linear differential equation obtained from a Wronskian, and improve the dependence on $k$ from exponential to polynomial in all three settings.

1. Every polynomial in the border of depth-$3$ circuits of size $s$ and top fan-in $k$ has an ABP of size $s^{O(k^2)}$; this is quasipolynomial even for $k=\mathrm{poly}(\log s)$.
2. There is an explicit hitting set for this border class of size $s^{O(k^2)}$.
3. There is an explicit polynomial of degree $d$ that is computed by a depth-$3$ circuit of size $O(kd)$ and top fan-in $k+1$, but requires border depth-$3$ circuits of top fan-in $k$ to have size $2^{\Omega(d/k^2)}$.

Finally, we show that the border of sums of $k$ powers of $\delta$-degree polynomials has depth-$6$ formulas of size $s^{\mathrm{poly}(k\delta)}$. This resolves a special case of an open question (Open Question 9) of Dutta and Lysikov's recent survey on debordering.



ISSN 1433-8092 | Imprint