Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-060 | 21st July 2015 22:07

Information Complexity and the Quest for Interactive Compression

RSS-Feed




Revision #1
Authors: Omri Weinstein
Accepted on: 21st July 2015 22:07
Downloads: 426
Keywords: 


Abstract:

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.



Changes to previous version:

A small error is fixed in the example showing that the analysis of BBCR's compression protocol is tight (end of Section 5.1).


Paper:

TR15-060 | 14th April 2015 07:16

Information Complexity and the Quest for Interactive Compression


Abstract:

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.



ISSN 1433-8092 | Imprint