Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > 2026:
All reports in year 2026:
TR26-001 | 1st January 2026
Théo Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff

Multilinear Algebraic Branching Programs and the Min-Partition Rank Method

It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mABPs). The best lower bounds in this setting are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the “min-partition rank” method introduced by ... more >>>




ISSN 1433-8092 | Imprint