ECCC-Report TR15-154https://eccc.weizmann.ac.il/report/2015/154Comments and Revisions published for TR15-154en-usWed, 23 Sep 2015 15:24:57 +0300
Paper TR15-154
| Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits |
Neeraj Kayal,
Vineet Nair,
Chandan Saha
https://eccc.weizmann.ac.il/report/2015/154We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:
1. There exists an explicit $n$-variate 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 \times 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 $n$-variate, degree $d$ polynomial computable by a poly($n$) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size $n^{\Omega(d)}$. This improves upon the quasi-polynomial separation of Raz & 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 (Raz 2006, Forbes & Shpilka 2013), while 2 is proved via a new adaptation of the dimension of the partial derivatives measure of Nisan & Wigderson (1997). Our lower bounds hold over any field. Wed, 23 Sep 2015 15:24:57 +0300https://eccc.weizmann.ac.il/report/2015/154