On the Optimal Compression of Sets in PSPACE

DOI10.1007/978-3-642-22953-4_6zbMath1342.68140arXiv1104.2816OpenAlexW1865843635MaRDI QIDQ3088270

Marius Zimand

Publication date: 19 August 2011

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.2816

zbMATH Keywords

compressionpseudo-random generatortime-bounded Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Low-depth witnesses are easy to find
• Language compression and pseudorandom generators
• Hardness vs randomness
• Resource bounded symmetry of information revisited
• Resource-Bounded Kolmogorov Complexity Revisited
• Kolmogorov Complexity in Randomness Extraction.
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Randomness Buys Depth for Approximate Counting

This page was built for publication: On the Optimal Compression of Sets in PSPACE