LIPIcs.ICALP.2018.4.pdf
- Filesize: 214 kB
- 1 pages
Document
Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)
Author
Richard Ryan Williams 
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Richard Ryan Williams. Lower Bounds by Algorithm Design: A Progress Report (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.4
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Circuit complexity
Keywords
- circuit complexity
- satisfiability
- derandomization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads