Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.