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 degree [Formula: see text] such that any [Formula: see text] computing it must have size [Formula: see text] for [Formula: see text] as low as [Formula: see text]. Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for [Formula: see text], we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear algebraic branching program (ABP). The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena [ Theor. Comput. Sci., 1041 (2025), 115214], which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs—for a polynomial of sufficiently low degree—would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant’s longstanding conjecture that the permanent polynomial cannot be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by [Formula: see text], then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind and Raja [ Chicago J. Theor. Comput. Sci., 22 (2016), 6] and Bhargav, Dwivedi, and Saxena [ Theor. Comput. Sci., 1041 (2025), 115214], as well as the works of Ramya and Rao [ Theor. Comput. Sci., 809 (2020), pp. 1–20] and Ghosal and Rao [in Proceedings of the International Computer Science Symposium in Russia, Springer, 2021, pp. 147–169], each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general [Formula: see text].