Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory

DOI10.1007/978-3-642-22685-4_21zbMATH Open1353.68104OpenAlexW92668834MaRDI QIDQ3087953

R. Ryan Williams

Publication date: 17 August 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22685-4_21

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Iterated lower bound formulas: a diagonalization-based approach to proof complexity ⋮ The Complexity of the Diagonal Problem for Recursion Schemes

This page was built for publication: Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory