Kayal, Neeraj
Arithmetic Circuit Complexity (Tutorial)
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 tauconjecture) aiming to prove lower bounds.
In the third part, we begin with a warmup 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 = {2828},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4501},
URN = {urn:nbn:de:0030drops45012},
doi = {10.4230/LIPIcs.STACS.2014.28},
annote = {Keywords: Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing}
}
05.03.2014
Keywords: 

Circuit complexity, arithmetic circuits, lower bounds, polynomial identity testing 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

05.03.2014 