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.CCC.2015.158
URN: urn:nbn:de:0030-drops-50617
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5061/
Go to the corresponding LIPIcs Volume Portal

Kayal, Neeraj ; Saha, Chandan

Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin

pdf-format:
13.pdf (0.7 MB)

Abstract

Shpilka and Wigderson (CCC 99) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field F of characteristic zero. We resolve this problem by proving a N^(Omega(d/t)) lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most t computing an explicit N-variate polynomial of degree d over F.

Meanwhile, Nisan and Wigderson (CC 97) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. Over fields of characteristic zero, we show a lower bound of N^(Omega(sqrt(d))) for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most N^(u), for any fixed u < 1. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most N).

BibTeX - Entry

@InProceedings{kayal_et_al:LIPIcs:2015:5061,
  author =	{Neeraj Kayal and Chandan Saha},
  title =	{{Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{158--208},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5061},
  URN =		{urn:nbn:de:0030-drops-50617},
  doi =		{10.4230/LIPIcs.CCC.2015.158},
  annote =	{Keywords: arithmetic circuits, depth three circuits, lower bound, bottom fanin}
}

Keywords: arithmetic circuits, depth three circuits, lower bound, bottom fanin
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI