[talks] A Garg general exam

[Melissa M. Lawson]

Ankit Garg will present his research seminar/general exam on Monday may 6 at 2PM in Room 402.  
The members of his committee are:  Mark Braverman (advisor), Zeev Dvir, and Moses Charikar. 
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.
----------------------------

Title : Communication Complexity of Small-Set Disjointness

Abstract : 

We obtain a tight bound of $\frac{2}{\ln 2}k \pm o(k)$ on the randomized communication complexity of disjointness of sets of size $\le k$. An asymptotic bound of $\Theta(k)$ was previously shown by H{\aa}stad and Wigderson.
One of the key components is the tight analysis for the zero-error information complexity of the 2-bit $AND$ function. This is obtained using a new local characterization of the zero-error information complexity function for two party communication problems. 

The lower bound for small-set disjointness requires an additional continuity argument for information complexity. It is trickier than disjointness, since we have to deal with very small information costs. Also the upper bound requires a nontrivial application of the ``information equals amortized communication" theorem.  

This is joint work with Mark Braverman, Denis Pankratov and Omri Weinstein. 


Reading List : 


Book : Computational Complexity - Sanjeev Arora and Boaz Barak

Papers : 

1. Information equals amortized communication - Mark Braverman, Anup Rao, FOCS 2011.

2. How to compress interactive communication - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao, STOC 2010

3. Interactive information complexity - Mark Braverman, STOC 2012

4. Communication lower bounds using directional derivatives - Alexander Sherstov, ECCC 2013

5. Direct products in communication complexity - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff, ECCC 2013.

6. Rounding Parallel Repetitions of Unique Games -  Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev and David Steurer, FOCS 2008.

7. Lower bounds on information complexity via zero-communication protocols and applications - I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. FOCS 2012.

8. Parallel Repetition in Projection Games and a Concentration Bound - Anup Rao, STOC 2008.

9. Algebrization: A New Barrier in Complexity Theory - S. Aaronson, A. Wigderson, STOC 2008.

10. On proving Super-Logarithmic Depth Lower Bounds via the Direct sum in Communication Complexity, M.Karchmer, R.Raz, A.Wigderson, Journal of Computational Complexity, 1995.

11. On ACC, R. Beigel and J. Tarui, Computational Complexity, 1994.