Short lists with short programs in short time

DOI10.1007/s00037-017-0154-2zbMath1390.68356arXiv1301.1547OpenAlexW2606059309MaRDI QIDQ1745959

Marius Zimand, Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin

Publication date: 18 April 2018

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

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

zbMATH Keywords

Kolmogorov complexityexpander graphonline matchinglist-approximator

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (10)

Algorithmic minimal sufficient statistics: a new approach ⋮ Enumerations including laconic enumerators ⋮ Some properties of antistochastic strings ⋮ Short lists with short programs from programs of functions and strings ⋮ Short lists for shortest descriptions in short time ⋮ Short lists with short programs in short time ⋮ Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs ⋮ Topological arguments for Kolmogorov complexity ⋮ On optimal language compression for sets in PSPACE/poly

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithmic minimal sufficient statistics: a new approach
• Short lists for shortest descriptions in short time
• Variations on Muchnik's conditional complexity theorem
• Extracting Kolmogorov complexity with applications to dimension zero-one laws
• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• On some games which are relevant to the theory of recursively enumerable sets
• 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
• Generating Kolmogorov random strings from sources with limited independence
• Game Arguments in Computability Theory and Algorithmic Information Theory
• Space-Bounded Kolmogorov Extractors
• COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY
• Kolmogorov Complexity in Randomness Extraction
• Optimal enumerations and optimal gödel numberings
• On Representatives of Subsets
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Short Lists with Short Programs in Short Time – A Short Proof
• Enumerations of the Kolmogorov function
• On a problem of K. Zarankiewicz
• Conditional complexity and codes

This page was built for publication: Short lists with short programs in short time