Abstract
We show an exponential separation between two wellstudied models of algebraic computation, namely readonce oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:
1. There exists an explicit nvariate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^{Omega(n)} size.
2. Any multilinear depth three circuit computing IMM_{n,d} (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^{Omega(d)} size. IMM_{n,d} can be easily computed by a poly(n,d) sized ROABP.
3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit nvariate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^{Omega(d)}. This improves upon the quasipolynomial separation result by Raz and Yehudayoff [2009] between these two models.
The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field.
BibTeX  Entry
@InProceedings{kayal_et_al:LIPIcs:2016:5747,
author = {Neeraj Kayal and Vineet Nair and Chandan Saha},
title = {{Separation Between Readonce Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {46:146:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5747},
URN = {urn:nbn:de:0030drops57475},
doi = {10.4230/LIPIcs.STACS.2016.46},
annote = {Keywords: multilinear depth three circuits, readonce oblivious algebraic branching programs, evaluation dimension, skewed partial derivatives, expander graphs,}
}
Keywords: 

multilinear depth three circuits, readonce oblivious algebraic branching programs, evaluation dimension, skewed partial derivatives, expander graphs, 
Collection: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) 
Issue Date: 

2016 
Date of publication: 

16.02.2016 