Name
Title | ||
|---|---|---|
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits |
Abstract | ||
|---|---|---|
We 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Ω(n) size.
(2) Any multilinear depth-three circuit computing IMMn,d (the iterated matrix multiplication polynomial formed by multiplying d, n × n symbolic matrices) has nΩ(d) size. IMMn,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Ω(d). This improves upon the quasi-polynomial separation of Reference [36] 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 [15, 33, 34, 36], while (2) is proved via a new adaptation of the dimension of the partial derivatives measure of Reference [32]. Our lower bounds hold over any field.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3369928 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
Multilinear depth-three circuits,evaluation dimension,expander graphs,iterated matrix multiplication,read-once oblivious algebraic branching programs,skewed partial derivatives | Discrete mathematics,Algebraic number,Electronic circuit,Multilinear map,Mathematics,Branching (version control) | Journal |
Volume | Issue | ISSN |
12 | 1 | 1942-3454 |
Citations | PageRank | References |
5 | 0.42 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Vineet Nair | 2 | 5 | 2.11 |
| Chandan Saha | 3 | 227 | 16.91 |