  In this paper, we study the structure of set-multilinear arithmetic circuits
and set-multilinear branching programs with the aim of showing lower bound
results. We define some natural restrictions of these models for which we are
able to show lower bound results. Some of our results extend existing lower
bounds, while others are new and raise open questions. More specifically, our
main results are the following:
  (1) We observe that set-multilinear arithmetic circuits can be transformed
into shallow set-multilinear circuits efficiently, similar to depth reduction
results of [VSBR83,RY08] for more general commutative circuits. As a
consequence, we note that polynomial size set-multilinear circuits have
quasi-polynomial size set-multilinear branching programs. We show that
\emph{narrow} set-multilinear ABPs (with a restricted number of set types)
computing the Permanent polynomial $\mathrm{PER}_n$ require $2^{n^{\Omega(1)}}$
size. A similar result for general set-multilinear ABPs appears difficult as it
would imply that the Permanent requires superpolynomial size set-multilinear
circuits. It would also imply that the noncommutative Permanent requires
superpolynomial size noncommutative arithmetic circuits.
  (2) Indeed, we also show that set-multilinear branching programs are
exponentially more powerful than \emph{interval} multilinear circuits (where
the index sets for each gate is restricted to be an interval w.r.t.\ some
ordering), assuming the sum-of-squares conjecture. This further underlines the
power of set-multilinear branching programs.
  (3) Finally, we consider set-multilinear circuits with restrictions on the
number of proof trees of monomials computed by it, and prove exponential lower
bounds results. This raises some new lower bound questions.
