Information Complexity and the Quest for Interactive Compression
Information Complexity and the Quest for Interactive Compression
复制标题
信息复杂性和交互式压缩的探索
DOI：
10.1145/2789149.2789161
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Omri Weinstein
中科院分区：
文献类型：
--
作者：
Omri Weinstein
信息复杂性是香农经典信息理论的互动类似物。近年来，该领域已成为证明强大的通信下限，并解决沟通复杂性和电路复杂性方面的一些主要开放问题的强大工具。信息复杂性的显着成就是了解基本直接总和和直接产品猜想的突破，旨在量化并行计算的能力。这项调查简要介绍了信息复杂性，概述了这些猜想的最新进展及其与压缩交互式协议的迷人问题的紧密关系。
Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is the breakthrough in understanding of the fundamental direct sum and direct product conjectures, which aim to quantify the power of parallel computation. This survey provides a brief introduction to information complexity, and overviews some of the recent progress on these conjectures and their tight relationship with the fascinating problem of compressing interactive protocols.