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.ICALP.2018.4
URN: urn:nbn:de:0030-drops-90088
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9008/
Go to the corresponding LIPIcs Volume Portal

Williams, Richard Ryan

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)

pdf-format:
LIPIcs-ICALP-2018-4.pdf (0.2 MB)

Abstract

In 2010, the author proposed a program for proving lower bounds in circuit complexity, via faster algorithms for circuit satisfiability and related problems. This talk will give an overview of how the program works, report on the successes of this program so far, and outline open frontiers that have yet to be resolved.

BibTeX - Entry

@InProceedings{williams:LIPIcs:2018:9008,
  author =	{Richard Ryan Williams},
  title =	{{Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9008},
  URN =		{urn:nbn:de:0030-drops-90088},
  doi =		{10.4230/LIPIcs.ICALP.2018.4},
  annote =	{Keywords: circuit complexity, satisfiability, derandomization}
}

Keywords: circuit complexity, satisfiability, derandomization
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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