On oracles and algorithmic methods for proving lower bounds

DOI10.4230/LIPICS.ITCS.2023.99MaRDI QIDQ6610372zbMATH OpenFDO

Authors Nikhil Vyas, Ryan Williams

Publication date 25 September 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2023.99

zbMATH Keywords

circuit complexityexponential hierarchymissing Stringoraclesrelativization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(2)

• Diagonalization Games
• Symmetric exponential time requires near-maximum circuit size

This page was built for publication: On oracles and algorithmic methods for proving lower bounds

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