INFORMATION THEORETIC RELAXATIONS IN COMPLEXITY THEORY

Abstract:

Since Shannon’s “A Mathematical Theory of Communication” [Sha48], 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 communication
complexity [BGPW13a, BGPW13c, BG14], hardness amplification of 2-prover
games [BG15], applications of quantum information complexity to the study of quantum
communication complexity of disjointness [BGK+15] and the use of strong data processing
inequalities to analyze communication complexity of distributed statistical estimation
[GMN14, BGM+16]. 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.