Short lists for shortest descriptions in short time

DOI10.1007/S00037-014-0090-3zbMath1366.68103arXiv1212.6104OpenAlexW2022038544MaRDI QIDQ475336

Jason Teutsch

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexitybipartite expander graphdisperser graphMuchnik's conditional complexity theoremonline matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (4)

Enumerations including laconic enumerators ⋮ Short lists with short programs in short time ⋮ Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs

Cites Work

• Variations on Muchnik's conditional complexity theorem
• Short lists with short programs in short time
• Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
• Lossless condensers, unbalanced expanders, and extractors
• Resource-Bounded Kolmogorov Complexity Revisited
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Short Lists with Short Programs in Short Time – A Short Proof
• Enumerations of the Kolmogorov function
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• An introduction to Kolmogorov complexity and its applications
• Conditional complexity and codes

This page was built for publication: Short lists for shortest descriptions in short time