Bounded relativization

DOI10.4230/LIPICS.CCC.2023.6MaRDI QIDQ6640340zbMATH OpenFDO

Authors Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Publication date 19 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2023.6

zbMATH Keywords

circuit lower boundderandomizationexplicit constructioninteractive proofspseudodeterministic algorithmsrelativization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(2)

• One-way functions and pKt complexity
• Symmetric exponential time requires near-maximum circuit size

This page was built for publication: Bounded relativization

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