2015/04/26 by Omri Weinstein, Weinstein, Omri
Computer Science · Engineering · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1504.06830
openalex publication_date 2015/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Information complexity is the interactive analogue of Shannon's classical\ninformation theory. In recent years this field has emerged as a powerful tool\nfor proving strong communication lower bounds, and for addressing some of the\nmajor open problems in communication complexity and circuit complexity. A\nnotable achievement of information complexity is the breakthrough in\nunderstanding of the fundamental direct sum and direct product conjectures,\nwhich aim to quantify the power of parallel computation. This survey provides a\nbrief introduction to information complexity, and overviews some of the recent\nprogress on these conjectures and their tight relationship with the fascinating\nproblem of compressing interactive protocols.\n