Revision #1 Authors: Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Accepted on: 9th August 2023 00:40

Downloads: 261

Keywords:

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^5s)$. Moreover, we show that for \textit{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 \cite{K19, CKSV22}, and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor \cite{KV22}.

While determinantal complexity and ABP complexity are classically known to be polynomially equivalent~\cite{MV97}, 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.

TR23-115 Authors: Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Publication: 8th August 2023 21:08

Downloads: 189

Keywords:

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^5s)$. Moreover, we show that for \textit{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 \cite{K19, CKSV22}, and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor \cite{KV22}.

While determinantal complexity and ABP complexity are classically known to be polynomially equivalent~\cite{MV97}, 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.