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

Williams, Richard Ryan

The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)

pdf-format:
7.pdf (0.4 MB)

Abstract

In circuit complexity, the polynomial method is a general approach to proving circuit lower bounds in restricted settings. One shows that functions computed by sufficiently restricted circuits are "correlated" in some way with a low-complexity polynomial, where complexity may be measured by the degree of the polynomial or the number of monomials. Then, results limiting the capabilities of low-complexity polynomials are extended to the restricted circuits.

Old theorems proved by this method have recently found interesting applications to the design of algorithms for basic problems in the theory of computing. This paper surveys some of these applications, and gives a few new ones.

BibTeX - Entry

@InProceedings{williams:LIPIcs:2014:4832,
  author =	{Richard Ryan Williams},
  title =	{{The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{47--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4832},
  URN =		{urn:nbn:de:0030-drops-48328},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.47},
  annote =	{Keywords: algorithm design, circuit complexity, polynomial method}
}

Keywords: algorithm design, circuit complexity, polynomial method
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

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