Determinants vs. Algebraic Branching Programs

We show that, for every homogeneous polynomial of degree \(d\) $d$ , if it has determinantal complexity at most \(s\) $s$ , then it can be computed by a homogeneous algebraic branching program (ABP) of size at most \(O(d^5s)\) $O(d^{5}s)$ . Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just \(s-1\) $s-1$ and the size is at most \(O(ds)\) $O(ds)$ .

Thus, for constant-degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant-degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree (Chatterjee et al. 2022; Kumar2019), and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor (Kumar& Volk 2022).

While determinantal complexity and ABP complexity are classically known to be polynomially equivalent (Mahajan & Vinay 1997), the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant-degree polynomials.