11:45, Seminar Hall Some Lower Bound Results for SetMultilinear Arithmetic Computations S. Raja Institute of Mathematical Sciences, Chennai. 280316 Abstract In this work, we study the structure of setmultilinear arithmetic circuits and setmultilinear 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. Specifically, our main results are the following: (1) We observe that setmultilinear arithmetic circuits can be transformed into shallow setmultilinear circuits efficiently, following [VSBR83,RY08]. Hence, polynomial size setmultilinear circuits have quasipolynomial size setmultilinear branching programs. (2) We show that \emph{knarrow} setmultilinear 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$ readonce oblivious ABPs computing $PER_n$ requires size $2^{\Omega(\frac{n}{r})}$. (3) We also show that setmultilinear 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 sumofsquares conjecture. This further underlines the power of setmultilinear branching programs. (4) Finally, we show exponential lower bounds for setmultilinear circuits with restrictions on the number of parse trees of monomials and prove exponential lower bounds results. This is a joint work with V. Arvind. ECCC link: http://eccc.hpiweb.de/report/2015/176/
