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.STACS.2014.28
URN: urn:nbn:de:0030-drops-45012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4501/
Go to the corresponding LIPIcs Volume Portal

Kayal, Neeraj

Arithmetic Circuit Complexity (Tutorial)

pdf-format:
59.pdf (0.3 MB)

Abstract

Arithmetic Circuits compute polynomial functions over their inputs via a sequence of arithmetic operations (additions, subtractions, multiplications, divisions, etc.). This tutorial will give an overview of arithmetic circuit complexity, focusing on the problem of proving lower bounds for arithmetic circuits.

In the first part, we begin with a few nontrivial upper bounds - matrix multiplication and the computation of symmetric polynomials. We then motivate some open problems we deal with in arithmetic circuit complexity. We will look at the problem of polynomial identity testing - motivating it by its application to bipartite matching, the problem of learning arithmetic circuits or circuit reconstruction and the problem of proving lower bounds for arithmetic circuits (motivating it via the problem of computing the permanent and the Hamiltonian polynomials). We will also see depth reduction for circuits - the tradeoffs involved (with respect to size) in squashing a circuit into one with smaller depth.

In the second part, we will see some classical lower bounds. In particular, we will see lower bounds for monotone arithmetic circuits and multilinear formulas. We then give a very quick overview of approaches being investigated (including geometric complexity theory and tau-conjecture) aiming to prove lower bounds.

In the third part, we begin with a warm-up by proving lower bounds for homogeneous depth three circuits. We will then see recent lower bounds for homogeneous depth four circuits and its consequences.

BibTeX - Entry

@InProceedings{kayal:LIPIcs:2014:4501,
  author =	{Neeraj Kayal},
  title =	{{Arithmetic Circuit Complexity (Tutorial)}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{28--28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4501},
  URN =		{urn:nbn:de:0030-drops-45012},
  doi =		{10.4230/LIPIcs.STACS.2014.28},
  annote =	{Keywords: Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing}
}

Keywords: Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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