[talks] Jieming Mao will present his Generals on May 8, 2015 at 1:30pm in CS 401

[Nicki Gotsis]

Jieming Mao will present his Generals on May 8, 2015 at 1:30pm in CS 401 

The members of his committee are: Mark Braverman(adviser), Sanjeev Arora, and Zeev Dvir. 

Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. 

Abstract: 
In this talk, I will focus on presenting the paper "Simulating Noisy Channel Interaction". This is joint work with Mark Braverman. In the paper, we show that T rounds of interaction over the binary symmetric channel BSC 1 / 2 − ε with feedback can be simulated with O(ε 2 T) rounds of interaction over a noiseless channel. We also introduce a more general “energy cost” model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely to carry over to energy complexity. Our main technical innovation is a self-reduction from simulating a noisy channel to simulating a slightly-less-noisy channel, which may have other applications in the area of interactive compression. 

Reading list: 
Books: 
Arora and Barak, Computational Complexity- A Modern Approach [Chapters 1-16] 
Kushilevitz and Nisan, Communication Complexity 

Papers: 
1: Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 67–76, 2010. 
2: Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In Proceedings of the 43rd annual ACM symposium on Theory of computing, pages 159–166. ACM, 2011. 
3: Mark Braverman and Anup Rao. Information equals amortized communication. In Rafail Ostrovsky, editor, FOCS, pages 748–757. IEEE, 2011. 
4: Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 151–160. ACM, 2013. 
5: Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 160–166. IEEE, 2012. 
6: Mark Braverman. A hard-to-compress interactive task? In 51st annual Allerton Conference on Communication, Control, and Computing, 2013. 
7: Mark Braverman and Klim Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. In Electronic Colloquium on Computational Complexity (ECCC), volume 21, page 7, 2014. 
8: Information lower bounds via self-reducibility 
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein CSR'13 
9: Interactive information complexity 
Mark Braverman STOC'12; 
10: Direct products in communication complexity Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff FOCS'13;