Thinking algorithmically about impossibility (invited talk)

DOI10.4230/LIPICS.CSL.2015.14MaRDI QIDQ5351947zbMATH OpenOpenAlexFDO

Authors Ryan Williams

Publication date 31 August 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.CSL.2015.14

zbMATH Keywords

circuit complexityderandomizationsatisfiability

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Algorithm analysis through proof complexity
• On the limit of some algorithmic approach to circuit lower bounds
• scientific article; zbMATH DE number 7701440
• Diagonalization strikes back: some recent lower bounds in complexity theory
• Lower bounds for unrestricted Boolean circuits: open problems

Cited in

(1)

• On the limit of some algorithmic approach to circuit lower bounds

This page was built for publication: Thinking algorithmically about impossibility (invited talk)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351947)