Prerona Chatterjee

Lower Bounds for Set-Multilinear Branching Programs

Abstract. In this paper, we prove super-polynomial lower bounds for the model of sum of ordered set-multilinear algebraic branching programs, each with a possibly different ordering ([Formula: see text]). Specifically, we give an explicit [Formula: see text]-variate polynomial of...