Lecture Schedule and Notes

Click on the titles for the lecture notes:

Date

Title

9/29/10Course organization. The entropy function, subadditivity.
10/4/10Combinatorial applications: bounding the binomial tail, counting subgraphs and perfect matchings.
10/6/10Relative entropy and mutual information.
10/11/10Graph entropy.
10/13/10Monotone formula lower bounds via graph entropy.
10/18/10Applications of graph entropy to perfect hashing and sorting. A lower bound for 2-query locally decodable codes.
10/20/10Shearer’s lemma, with applications to counting graph embeddings and the size of intersecting families.
10/25/10A lower bound on the randomized communication complexity of set disjointness + direct sums in randomized communication complexity
10/27/10A lower bound on the randomized communication complexity of set disjointness + direct sums in randomized communication complexity (contd.)
11/1/10The parallel repetition theorem.
11/3/10Rounds in communication complexity revisited. N. Nisan, A. Wigderson. Presented by Thach.
11/8/10On data structures and asymmetric communication complexity. P. Miltersen, N. Nisan, S. Safra, A. Wigderson. Presented by Johnny.
11/10/10Logarithmic lower bounds in the cell-probe model. E. Demaine, M. Pătraşcu. Presented by Kevin. Kevin’s notes.
11/15/10An optimal randomised cell probe lower bound for approximate nearest neighbour searching. A. Chakrabarti, O. Regev. Presented by Mohammad.
11/17/10The space complexity of approximating the frequency moments. N. Alon, Y. Matias, M. Szegedy. Presented by Prasang.
11/22/10A constructive proof of the general Lovasz local lemma. R. Moser, G. Tardos. Presented by Elisa.
11/24/10Unbalanced expanders and randomness extractors from parvaresh-vardy codes. V. Guruswami, C. Umans, S. Vadhan. Presented by Punya.
11/29/10Pseudorandom generators for regular branching programs. M. Braverman, A. Rao, R. Raz, A. Yehudayoff. Presented by Widad.
12/1/10Computational analogues of entropy. B. Barak, R. Shaltiel, A. Wigderson. Presented by Lukas.
12/6/10Compression of Samplable Sources. L. Trevisan, S. Vadhan, D. Zuckerman. Presented by Abhay.
12/8/10Efficiency improvements in constructing pseudorandom generators from one-way functions. I. Haitner, O. Reingold, S. Vadhan. Presented by Alex.
 
Edit the following files to make lecture notes:
TeX file icon lecture1.tex11K Download
TeX file icon preamble.tex5K Download
Send questions about this workspace to Anup Rao.