  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}$.
