Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-115 | 9th August 2023 00:40

Determinants vs. Algebraic Branching Programs

RSS-Feed




Revision #1
Authors: Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
Accepted on: 9th August 2023 00:40
Downloads: 261
Keywords: 


Abstract:

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.


Paper:

TR23-115 | 8th August 2023 20:34

Determinants vs. Algebraic Branching Programs





TR23-115
Authors: Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
Publication: 8th August 2023 21:08
Downloads: 189
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint