首页    期刊浏览 2025年06月18日 星期三
登录注册

文章基本信息

  • 标题:Randomized communication complexity of appropximating Kolmogorov complexity
  • 本地全文:下载
  • 作者:Nikolay Vereshchagin
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string x and Bob a binary string y, both of length n, and they want to compute or approximate Kolmogorov complexity C(xy) of x conditional to y. It is easy to show that deterministic communication complexity of approximating C(xy) with precision is at least n−2−O(1). The above referenced paper asks what is randomized communication complexity of this problem and shows that for r-round randomized protocols its communication complexity is at least ((n)1r)

  • 关键词:Conditional Kolmogorov complexity; lower bounds; Randomized communication protocols
国家哲学社会科学文献中心版权所有