[talks] Ankit Garg will present his Pre-FPO on Thursday, February 4, 2016 at 1:30 pm in CS 402.

[Nicki Gotsis]

Ankit Garg will present his Pre-FPO on Thursday, February 4 at 1:30 pm in CS 402. 

The members of his committee are Mark Braverman (adviser), Sanjeev Arora, Zeev Dvir, Ran Raz (IAS) and Avi Wigderson (IAS).

Everyone is invited to attend his talk.  The talk title and abstract follow below:

Title: 
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. In the first part of talk, I will talk about a new information theoretic framework for proving parallel repetition of 2-prover 1-round games. Using this framework, we can resolve the open question about parallel repetition of small value games. This is based on joint work with Mark Braverman. In the second part of the talk, I will talk about near optimal round-communication tradeoffs for quantum communication complexity of disjointness. The techniques involved in the proof include quantum information complexity and the self reducibility of disjointness. This is based on joint work with Mark Braverman, Young Kun Ko, Jieming Mao and Dave Touchette.