Abstract
Tavenas has recently proved that any n^{O(1)}variate and degree n polynomial in VP can be computed by a depth4 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 depth4 circuits. Soon after Tavenas' result, for two different explicit polynomials, depth4 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 depth4 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 depth4 circuits.
In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies this property would achieve a similar depth4 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 depth4 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^2variate 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: depth4 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 = {{Depth4 Lower Bounds, Determinantal Complexity: A Unified Approach}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {239250},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4461},
URN = {urn:nbn:de:0030drops44610},
doi = {10.4230/LIPIcs.STACS.2014.239},
annote = {Keywords: Arithmetic Circuits, Determinantal Complexity, Depth4 Lower Bounds}
}
Keywords: 

Arithmetic Circuits, Determinantal Complexity, Depth4 Lower Bounds 
Collection: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) 
Issue Date: 

2014 
Date of publication: 

05.03.2014 