Information Theoretic Relaxations in Complexity Theory

Abstract

Since Shannon’s “A Mathematical Theory of Communication”, information theory has found applicability in a wide range of scientific disciplines. Over the past two decades, information theory has reemerged in theoretical computer science as a mathematical tool with applications to streaming algorithms, data structures, communication complexity etc. Properties of mutual information such as additivity and chain rule play an important role in these applications. In this thesis, we apply information theoretic tools to study various problems in complexity theory. These include the study of information complexity and com- munication complexity, hardness amplification of 2-prover games, applications of quantum information complexity to the study of quantum communication complexity of disjointness and the use of strong data process- ing inequalities to analyze communication complexity of distributed statistical estimation. Along the way, we also develop several information theoretic tools such as correlated sampling theorems, subadditivity properties of information and quantum information cost etc. which could be of independent interest.