Name
Abstract | ||
|---|---|---|
We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in VP. Our results hold for the Iterated Matrix Multiplication polynomial - in particular we show that any homogeneous depth 4 circuit computing the (1, 1) entry in the product of n generic matrices of dimension nO(1) must have size nΩ(√n). Our results strengthen previous works in two significant ways. 1) Our lower bounds hold for a polynomial in VP. Prior to our work, Kayal et al [KLSSa] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in VNP. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in VP was the bound of nΩ(log n) by [KLSSb], [KLSSa]. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Koi12] and Tavenas [Tav13] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fanin). 2) Our lower bound holds over all fields. The lower bound of [KLSSa] worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was nΩ(log n) [KLSSb], [KLSSa]. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.46 | Foundations of Computer Science |
Keywords | DocType | Volume |
computational complexity,digital arithmetic,iterative methods,matrix multiplication,VNP,arithmetic circuits,depth reduction,exponential lower bounds,generic matrices,homogeneous depth 4 circuits,homogeneous depth circuits,iterated matrix multiplication polynomial,Lower bounds,arithmetic circuits,depth reduction | Journal | 46 |
Issue | ISSN | Citations |
1 | 0272-5428 | 21 |
PageRank | References | Authors |
0.70 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Shubhangi Saraf | 2 | 263 | 24.55 |