Conditional complexity and codes

DOI10.1016/S0304-3975(01)00033-0zbMath0992.68082OpenAlexW2050348803MaRDI QIDQ5958284

Andrej A. Muchnik

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00033-0

zbMATH Keywords

hashingexpandersconditional Kolmogorov complexityminimal program

Mathematics Subject Classification ID

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

Related Items (18)

Non-reducible descriptions for conditional Kolmogorov complexity ⋮ Individual communication complexity ⋮ Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem ⋮ Stability of properties of Kolmogorov complexity under relativization ⋮ INFORMATION DISTANCE AND ITS APPLICATIONS ⋮ Nonreducible descriptions for the conditional Kolmogorov complexity ⋮ Variations on Muchnik's conditional complexity theorem ⋮ Information disclosure in the framework of Kolmogorov complexity ⋮ Short lists for shortest descriptions in short time ⋮ Kolmogorov Complexity as a Language ⋮ Short lists with short programs in short time ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Unnamed Item ⋮ Capturing one-way functions via NP-hardness of meta-complexity ⋮ On joint conditional complexity (entropy) ⋮ Kolmogorov complexity and cryptography ⋮ Topological arguments for Kolmogorov complexity ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• On a complexity of the formula \((A\bigvee B) \Rightarrow C\)
• Information distance
• Independent minimum length programs to translate between given strings
• Unnamed Item
• Unnamed Item

This page was built for publication: Conditional complexity and codes