Abstract
We show an Ω̃(n^2.5) lower bound for general depth four arithmetic circuits computing an explicit nvariate degreeΘ(n) multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey [Amir Shpilka and Amir Yehudayoff, 2010], no superquadratic lower bound was known for depth four circuits over fields of characteristic ≠ 2 before this work. The previous best lower bound is Ω̃(n^1.5) [Abhijat Sharma, 2017], which is a slight quantitative improvement over the roughly Ω(n^1.33) bound obtained by invoking the superlinear lower bound for constant depth circuits in [Ran Raz, 2010; Victor Shoup and Roman Smolensky, 1997].
Our lower bound proof follows the approach of the almost cubic lower bound for depth three circuits in [Neeraj Kayal et al., 2016] by replacing the shifted partials measure with a suitable variant of the projected shifted partials measure, but it differs from [Neeraj Kayal et al., 2016]’s proof at a crucial step  namely, the way "heavy" product gates are handled. Loosely speaking, a heavy product gate has a relatively high fanin. Product gates of a depth three circuit compute products of affine forms, and so, it is easy to prune Θ(n) many heavy product gates by projecting the circuit to a lowdimensional affine subspace [Neeraj Kayal et al., 2016; Amir Shpilka and Avi Wigderson, 2001]. However, in a depth four circuit, the second (from the top) layer of product gates compute products of polynomials having arbitrary degree, and hence it was not clear how to prune such heavy product gates from the circuit. We show that heavy product gates can also be eliminated from a depth four circuit by projecting the circuit to a lowdimensional affine subspace, unless the heavy gates together account for Ω̃(n^2.5) size. This part of our argument is inspired by a wellknown greedy approximation algorithm for the weighted setcover problem.
BibTeX  Entry
@InProceedings{gupta_et_al:LIPIcs:2020:12575,
author = {Nikhil Gupta and Chandan Saha and Bhargav Thankey},
title = {{A SuperQuadratic Lower Bound for Depth Four Arithmetic Circuits}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {23:123:31},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12575},
URN = {urn:nbn:de:0030drops125757},
doi = {10.4230/LIPIcs.CCC.2020.23},
annote = {Keywords: depth four arithmetic circuits, Projected Shifted Partials, superquadratic lower bound}
}
Keywords: 

depth four arithmetic circuits, Projected Shifted Partials, superquadratic lower bound 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 