On optimal language compression for sets in PSPACE/poly

DOI10.1007/S00224-014-9535-YzbMath1397.68111arXiv1304.1005OpenAlexW2092912590MaRDI QIDQ2354585

N. V. Vinodchandran, Marius Zimand

Publication date: 20 July 2015

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

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

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compression of samplable sources
• Language compression and pseudorandom generators
• Hardness vs randomness
• Short lists with short programs in short time
• On symmetry of information and polynomial time invertibility
• Resource bounded symmetry of information revisited
• Resource-Bounded Kolmogorov Complexity Revisited
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Computational Complexity
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: On optimal language compression for sets in PSPACE/poly