Revision #1 Authors: Vikraman Arvind, Raja S

Accepted on: 2nd March 2016 16:42

Downloads: 675

Keywords:

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:

(1) We observe that set-multilinear arithmetic circuits can be transformed into shallow set-multilinear circuits efficiently, following \cite{VSBR83,RY08}. Hence, polynomial size set-multilinear circuits have quasi-polynomial size set-multilinear branching programs.

(2) We show that \emph{k-narrow} set-multilinear ABPs computing the Permanent polynomial

$\mathrm{PER}_n$ (or determinant $\mathrm{DET}_n$) require $2^{\Omega(k)}$

size. As a consequence, we show that sum of $r$ read-once oblivious ABPs computing $\mathrm{PER}_n$ requires size $2^{\Omega(\frac{n}{r})}$.

(3) 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.

(4) Finally, we show exponential lower bounds for set-multilinear circuits with restrictions on the number of parse trees of monomials

and prove exponential lower bounds results.

Some of proofs are rewritten and parameters are improved.

TR15-176 Authors: Vikraman Arvind, Raja S

Publication: 6th November 2015 08:10

Downloads: 928

Keywords:

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.