2023/08/08 by Abhranil Chatterjee, Mrinal Kumar, Chatterjee, Abhranil +3 · 3 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2308.04599
openalex publication_date 2023/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for every homogeneous polynomial of degree d, if it has determinantal complexity at most s, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O(d5s). Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s-1 and the size is at most 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, and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent, 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.