scientific article; zbMATH DE number 7754310

DOI10.4086/toc.2023.v019a004OpenAlexW4387349023MaRDI QIDQ6054746

Shuichi Hirahara

Publication date: 25 October 2023

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2023.v019a004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

pseudorandom generatorminimum circuit size problemhitting set generatormeta-complexityLevin's Kt complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Boosting and hard-core set construction
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Circuit minimization problem
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Average Case Complete Problems
• Randomness conservation inequalities; information and independence in mathematical theories
• Locally Decodable Codes

This page was built for publication: