{"id":"arxiv/2604.00746","url":"https://arxiv.org/abs/2604.00746","tags":["cs.CC","math.CO","math.PR"],"score":0,"title":"An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds","domain":"cs.CC","source":"arxiv","authors":["Deepanshu Kush"],"reviews":0,"subject":"cs.CC","summary":"Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a longstanding open problem in algebraic complexity theory. All known multilinear lower bounds rely on the min-partition rank method, and the best bounds against mABPs have remained quadratic (Alon, Kumar, and Volk, Combinatorica 2020). We show that the min-partition rank method cannot prove superpolynomial mABP lower bounds: there exists a full-rank multilinear polynomial computable by a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}