[talks] Jonathan Schneider will present his Generals on May 6, 2015 at 2pm in CS 302

[Nicki Gotsis]

Jonathan Schneider will present his Generals on May 6, 2015 at 2pm in CS 302.

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

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

Abstract:
The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this talk, I will describe joint work with Mark Braverman where we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error α>0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.


Reading List :
1. Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. 
2. Thomas Cover, Joy Thomas. Elements of Information Theory.
3. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive
communication.
4. Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information
to exact communication.
5. Mark Braverman and Anup Rao. Information equals amortized communication 
6. M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic
depth.
7. Anat Ganor, Gillat Kol, Ran Raz. Exponential separation of Information and Communication.
8. Rahul Jain. New strong direct product results in communication complexity
9. Ran Raz. A parallel repetition theorem.
10. Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive
communication.
11. Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial
noise.
12. Gillat Kol, Ran Raz. Interactive Channel Capacity.