[talks] Ankit Garg will present his FPO on Wednesday, June 15, 2016 at 11am in CS 302

[Nicki Gotsis]

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.