Ankit Garg will present his FPO, "INFORMATION THEORETIC RELAXATIONS IN COMPLEXITY THEORY" on Wednesday, June 15, 2016 at 11am in CS 302. The members of his committee are Mark Braverman (adviser), Readers: Zeev Dvir and Ran Raz (Weizmann Institute of Science); Nonreaders: Avi Wigderson (Math) and Bernard Chazelle. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The abstract follow below. 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.