Randomized communication complexity of approximating Kolmogorov complexity

DOI10.1007/978-3-319-06686-8_28MaRDI QIDQ4981175zbMATH OpenOpenAlexFDO

Authors Nikolai K. Vereshchagin

Publication date 24 June 2014

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06686-8_28

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Individual communication complexity
• Kolmogorov complexity and combinatorial methods in communication complexity
• Kolmogorov Complexity and Combinatorial Methods in Communication Complexity
• Kolmogorov Complexity with Error
• On approximate uncomputability of the Kolmogorov complexity function

Cited in

(4)

• On approximate uncomputability of the Kolmogorov complexity function
• Average and randomized communication complexity
• Kolmogorov Complexity with Error
• The communication complexity of pointer chasing: applications of entropy and sampling

This page was built for publication: Randomized communication complexity of approximating Kolmogorov complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4981175)