Randomness and Intractability in Kolmogorov Complexity
From MaRDI portal
Publication:5091181
DOI10.4230/LIPIcs.ICALP.2019.32OpenAlexW2964451256MaRDI QIDQ5091181
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.32
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Kolmogorov complexity and the second incompleteness theorem
- Randomness vs time: Derandomization under a uniform assumption
- Pseudorandomness and average-case complexity via uniform reductions
- The Complexity of Complexity
- The Surprise Examination Paradox and the Second Incompleteness Theorem
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hierarchies for semantic classes
- Unconditional Lower Bounds against Advice
- Randomness conservation inequalities; information and independence in mathematical theories
- Quantum Kolmogorov complexity based on classical descriptions
- Information-Theoretic Limitations of Formal Systems
- Pseudodeterministic constructions in subexponential time
- Learning algorithms from natural proofs
- Power from Random Strings
- An introduction to Kolmogorov complexity and its applications
- Pseudo-random generators for all hardnesses
- Quantum Kolmogorov complexity
This page was built for publication: Randomness and Intractability in Kolmogorov Complexity
