In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$).
Specifically, we give an explicit $nd$-variate polynomial of degree $d$ such that any $\sum \mathsf{smABP}$ computing it must have size $n^{\omega(1)}$ for $d$ as low as $\omega(\log n)$. Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for $d = \poly(n)$, 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 ABP.

The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (to appear in TAMC, 2024), 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 can not be computed efficiently by ABPs.
More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by $O(\log n/ \log \log n)$, then it would imply super-polynomial lower bounds against general ABPs.

Our results strengthen the works of Arvind \& Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi \& Saxena (to appear in TAMC, 2024), as well as the works of Ramya \& Rao (Theor. Comput. Sci., 2020) and Ghoshal \& Rao (International Computer Science Symposium in Russia, 2021), 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 $\sum \mathsf{smABP}$.

In this paper, we prove the first \emph{super-polynomial} and, in fact, \emph{exponential} lower bound for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering ($\sum \mathsf{smABP}$).
In particular, we give an explicit polynomial such that any $\sum \mathsf{smABP}$ computing it must have exponential size.
This result generalizes the seminal work of Nisan (STOC 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP.

The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (2023), 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 can not be computed efficiently by ABPs.
More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by $O(\log n/ \log \log n)$, then it would imply super-polynomial lower bounds against general ABPs.
In this paper, we show super-polynomial lower bounds against this model for a polynomial whose degree is as small as $\omega(\log n)$.
Prior to our work, showing such lower bounds was open \emph{irrespective} of the assumption on the degree.

Our results strengthen the works of Arvind \& Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi \& Saxena (2023), as well as the works of Ramya \& Rao (Theor. Comput. Sci., 2020) and Ghoshal \& Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related versions of this model.
They also strongly answer an open question from the former two, which asked to prove super-polynomial lower bounds for $\sum \mathsf{smABP}$.

We have learned about related works that we were not aware of (Ramya & Rao (Theor. Comput. Sci., 2020) and Ghoshal & Rao (International Computer Science Symposium in Russia, 2021)).

These works prove exponential lower bounds for sums of ROABPs. We prove such bounds for sums of set-multilinear ABPs, which are closely related to sums of ROABPs but are not equivalent. In view of that, our claim in the original abstract (and the original title) that we are the first to prove exponential lower bounds for sums of ROABPs is incorrect. Nonetheless, the focus (and indeed all the theorems we prove) concern set-multilinear ABPs for which the previous works and techniques do not apply. In particular, these works do not change the novelty or strength of our results. These papers also use the term set-multilinearity, but they refer to a completely different model (and it remains unclear whether their techniques could be adapted to the set-multilinear setting). Furthermore, the polynomials for which they prove their results are not set-multilinear with respect to any partition of the variables.

We have modified the paper to discuss these new results (see section 1.5 for comparison of models and section 1.6 for related work, along with slightly changed title and abstract).

In this paper, we prove the first super-polynomial and, in fact, exponential lower bound for the model of sum of read-once oblivious algebraic branching programs (ROABPs). In particular, we give an explicit polynomial such that any sum of ROABPs
(equivalently, sum of *ordered* set-multilinear branching programs, each with a possibly different ordering) computing it must have exponential size.

This result generalizes the seminal work of Nisan (STOC 1991), which proved an exponential lower bound for a single ROABP. It also strengthens the work of Arvind and Raja (Chic. J. Theor. Comput. Sci., 2016), as well as the work of Bhargav, Dwivedi, and Saxena (2023), both of which established lower bounds against certain restricted versions of this model, and strongly answers an open question from both papers that asked to prove super-polynomial lower bounds for the corresponding *unrestricted* model.

The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (2023), 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 can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by $O(\log n/ \log \log n)$, then it would imply super-polynomial lower bounds against general ABPs.

In this paper, we show super-polynomial lower bounds against this model for a polynomial whose degree is as small as $\omega(\log n)$. Prior to our work, showing such lower bounds was open *irrespective* of the assumption on the degree.