License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.5
URN: urn:nbn:de:0030-drops-76858
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7685/
Go to the corresponding LIPIcs Volume Portal


Mahajan, Meena

Arithmetic Circuits: An Overview (Invited Talk)

pdf-format:
LIPIcs-CSL-2017-5.pdf (0.2 MB)


Abstract

This talk reviews recent developments in algebraic complexity theory. It outlines some major results concerning structure, completeness, closure, and lower bounds. It describes some techniques that have been central to obtaining these results, including extreme depth reduction, partial derivatives, and padding.

BibTeX - Entry

@InProceedings{mahajan:LIPIcs:2017:7685,
  author =	{Meena Mahajan},
  title =	{{Arithmetic Circuits: An Overview (Invited Talk)}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7685},
  URN =		{urn:nbn:de:0030-drops-76858},
  doi =		{10.4230/LIPIcs.CSL.2017.5},
  annote =	{Keywords: algebraic complexity, circuits, formulas, branching programs, determinant, permanent}
}

Keywords: algebraic complexity, circuits, formulas, branching programs, determinant, permanent
Seminar: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 14.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI