#

### Volume 2016

#### Article 6

Published by the Department of Computer Science, The University of Chicago.

#### Some Lower Bound Results for Set-Multilinear Arithmetic Computations

V. Arvind

The Institute of Mathematical Sciences,

Chennai 600113, India;

`arvind AT imsc DOT res DOT in `
S. Raja

The Institute of Mathematical Sciences,

Chennai 600113, India;

`rajas AT imsc DOT res DOt in`

*April 28, 2016*
#### Abstract

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. Specifically, our main results are the
following:
- We observe that set-multilinear arithmetic circuits can be
transformed into shallow set-multilinear circuits efficiently,
following [VSBR83, RY08]. Hence, polynomial size set-multilinear
circuits have quasi-polynomial size set-multilinear branching
programs.
- We show that
*k-narrow* set-multilinear ABPs
computing the Permanent polynomial
$PER_n$ (or determinant $DET_n$) require $2^{\Omega(k)}$
size. As a consequence, we show that sum of $r$ read-once oblivious ABPs
computing $PER_n$ requires size $2^{\Omega(\frac{n}{r})}$.
- We also show that set-multilinear branching programs are exponentially more
powerful than
*interval* multilinear circuits (where the index sets for
each gate are 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.
- Finally, we show exponential lower bounds for set-multilinear circuits with
restrictions on the number of parse trees of monomials and prove exponential
lower bound results.

- The article:
**PDF** (300 KB)
- Source material: ZIP (76 KB)
**BibTeX** entry for this
article (334 bytes)

Submitted November 4, 2015, revised March 2, 2016 and April 17, 2016, published April 28, 2016.

Volume 2016, Article 5
Article 7

Volume 2016
Published articles