2026-07-23T13:24:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9008 2024-03-06T10:43:08Z ddc:004 open_access

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper) Williams, Richard Ryan circuit complexity satisfiability derandomization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Richard Ryan Williams 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.4 urn:nbn:de:0030-drops-90088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode