License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.239
URN: urn:nbn:de:0030-drops-44610
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4461/
Chillara, Suryajith ;
Mukhopadhyay, Partha
Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach
Abstract
Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 SigmaPi^[O(sqrt{n})]SigmaPi^{[sqrt{n}]} circuit of size 2^{O(n^{1/2}.log(n))} [Tavenas, 2013]. So, to prove that VP is not equal to VNP it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{omega(n^{1/2}.log(n))} size depth-4 circuits. Soon after Tavenas' result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{Omega(n^{1/2}.log(n))} have been proved (see [Kayal, Saha, and Saptharishi, 2013] and [Fournier et al., 2013]). In particular, using combinatorial design [Kayal et al., 2013] construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{Omega(n^{1/2}.log(n))} and [Fournier et al., 2013] show that the iterated matrix multiplication polynomial (which is in VP) also requires 2^{Omega(n^{1/2}.log(n))} size depth-4 circuits.
In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies this property would achieve a similar depth-4 circuit size lower bound. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a simple unified lower bound analysis for the above mentioned polynomials.
Another goal of this paper is to compare our current knowledge of the depth-4 circuit size lower bounds and the determinantal complexity lower bounds. Currently the best known determinantal complexity lower bound is Omega(n^2) for Permanent of a nxn matrix (which is a n^2-variate and degree n polynomial) [Cai, Chen, and Li, 2008]. We prove that the determinantal complexity of the iterated matrix multiplication polynomial is Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. Our result also settles the determinantal complexity of the iterated matrix multiplication polynomial to Theta(dn).
To the best of our knowledge, a Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for any constant d>1 [Jansen, 2011].
BibTeX - Entry
@InProceedings{chillara_et_al:LIPIcs:2014:4461,
author = {Suryajith Chillara and Partha Mukhopadhyay},
title = {{Depth-4 Lower Bounds, Determinantal Complexity: A Unified Approach}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {239--250},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4461},
URN = {urn:nbn:de:0030-drops-44610},
doi = {10.4230/LIPIcs.STACS.2014.239},
annote = {Keywords: Arithmetic Circuits, Determinantal Complexity, Depth-4 Lower Bounds}
}
|
Keywords: |
|
Arithmetic Circuits, Determinantal Complexity, Depth-4 Lower Bounds |
|
Collection: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
05.03.2014 |
