Conditional complexity and codes
From MaRDI portal
Publication:5958284
DOI10.1016/S0304-3975(01)00033-0zbMath0992.68082OpenAlexW2050348803MaRDI QIDQ5958284
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
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
This page was built for publication: Conditional complexity and codes