Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BHARGAV THANKEY:
All reports by Author Bhargav Thankey:

TR20-028 | 27th February 2020
Nikhil Gupta, Chandan Saha, Bhargav Thankey

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>




ISSN 1433-8092 | Imprint