2026-07-26T17:25:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19555 2024-03-06T11:04:19Z ddc:004 open_access

Determinants vs. Algebraic Branching Programs Chatterjee, Abhranil Kumar, Mrinal Volk, Ben Lee Determinant Algebraic Branching Program Lower Bounds Singular Variety 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(d⁵s). 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 [Mrinal Kumar, 2019; Prerona Chatterjee et al., 2022], and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor [Mrinal Kumar and Ben Lee Volk, 2022]. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent [Meena Mahajan and V. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhranil Chatterjee and Mrinal Kumar and Ben Lee Volk 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.27 urn:nbn:de:0030-drops-195550 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode