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

Author Richard Ryan Williams



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.4.pdf
  • Filesize: 214 kB
  • 1 pages

Document Identifiers

Author Details

Richard Ryan Williams
  • MIT EECS and CSAIL, 32 Vassar St, Cambridge, MA 02139 USA

Cite AsGet 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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail