A super-quadratic lower bound for depth four arithmetic circuits

Nikhil Gupta, Chandan Saha, Bhargav Thankey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show an Ω(e n2.5) lower bound for general depth four arithmetic circuits computing an explicit n-variate degree-Θ(n) multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey [88], no super-quadratic lower bound was known for depth four circuits over fields of characteristic 6= 2 before this work. The previous best lower bound is Ω(e n1.5) [85], which is a slight quantitative improvement over the roughly Ω(n1.33) bound obtained by invoking the super-linear lower bound for constant depth circuits in [73,86]. Our lower bound proof follows the approach of the almost cubic lower bound for depth three circuits in [53] by replacing the shifted partials measure with a suitable variant of the projected shifted partials measure, but it differs from [53]'s proof at a crucial step - namely, the way “heavy” product gates are handled. Loosely speaking, a heavy product gate has a relatively high fan-in. 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 low-dimensional affine subspace [53,87]. 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 low-dimensional affine subspace, unless the heavy gates together account for Ω(e n2.5) size. This part of our argument is inspired by a well-known greedy approximation algorithm for the weighted set-cover problem.

Original languageEnglish (US)
Title of host publication35th Computational Complexity Conference, CCC 2020
EditorsShubhangi Saraf
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771566
DOIs
StatePublished - Jul 1 2020
Event35th Computational Complexity Conference, CCC 2020 - Virtual, Online, Germany
Duration: Jul 28 2020Jul 31 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume169
ISSN (Print)1868-8969

Conference

Conference35th Computational Complexity Conference, CCC 2020
CountryGermany
CityVirtual, Online
Period7/28/207/31/20

Keywords

  • Depth four arithmetic circuits
  • Projected Shifted Partials
  • Super-quadratic lower bound

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A super-quadratic lower bound for depth four arithmetic circuits'. Together they form a unique fingerprint.

Cite this