The hardest explicit construction

DOI10.1109/FOCS52979.2021.00051MaRDI QIDQ6943499zbMATH OpenFDO

Authors Oliver Korten

Publication date 13 August 2025

Full work available at URL https://doi.org/10.1109/FOCS52979.2021.00051

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Proceedings, conferences, collections, etc. pertaining to information and communication theory (94-06)

Cited in

(8)

• Range avoidance for low-depth circuits and connections to pseudorandomness
• Symmetric exponential time requires near-maximum circuit size
• Oblivious complexity classes revisited: lower bounds and hierarchies
• Exponential-size circuit complexity is comeager in symmetric exponential time
• Counting martingales for measure and dimension in complexity classes
• Provably total functions in the polynomial hierarchy
• How to construct random strings
• Avoiding range via Turán-type bounds

This page was built for publication: The hardest explicit construction

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