### Volume 2016

#### 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)