scientific article; zbMATH DE number 7754310

DOI10.4086/TOC.2023.V019A004MaRDI QIDQ6054746zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

hitting set generatorLevin's Kt complexitymeta-complexityminimum circuit size problempseudorandom generator

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7561748
• Pseudorandom Generators in Propositional Proof Complexity
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• The complexity of constructing pseudorandom generators from hard functions
• On the complexity of constructing pseudorandom functions (especially when they don't exist)
• General pseudo-random generators from weaker models of computation
• Pseudorandomness and Combinatorial Constructions
• Publication:3359634
• scientific article; zbMATH DE number 2081080
• Practical construction and analysis of pseudo-randomness primitives

Cites work

• Average Case Complete Problems
• Boosting and hard-core set construction
• Circuit minimization problem
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• scientific article; zbMATH DE number 3778752 (Why is no real title available?)
• Locally decodable codes
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Randomness conservation inequalities; information and independence in mathematical theories

This page was built for publication:

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