On the Optimal Compression of Sets in PSPACE

DOI10.1007/978-3-642-22953-4_6zbMath1342.68140arXiv1104.2816MaRDI 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

compression; pseudo-random generator; time-bounded Kolmogorov complexity

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

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

Related Items

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

Cites Work

• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item