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.
@InProceedings{williams:LIPIcs.ICALP.2018.4, author = {Williams, Richard Ryan}, title = {{Lower Bounds by Algorithm Design: A Progress Report}}, 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 = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.4}, URN = {urn:nbn:de:0030-drops-90088}, doi = {10.4230/LIPIcs.ICALP.2018.4}, annote = {Keywords: circuit complexity, satisfiability, derandomization} }
Feedback for Dagstuhl Publishing