All Catalyst Web Tools--except WebQ Survey and GradeBook--will be retired.
View timeline and details
.
Jump to main page content.
Your Tools
Help
Log in
CommonView
CSE 533: Information Theory in Computer Science
Home
Course Description
Paper List
Lecture Schedule and Notes
Homeworks
Lecture Schedule and Notes
Click on the titles for the lecture notes:
Date
Title
9/29/10
Course organization.
The entropy function, subadditivity.
10/4/10
Combinatorial applications: bounding the binomial tail, counting subgraphs and perfect matchings.
10/6/10
Relative entropy and mutual information.
10/11/10
Graph entropy.
10/13/10
Monotone formula lower bounds via graph entropy.
10/18/10
Applications of graph entropy to perfect hashing and sorting. A lower bound for 2-query locally decodable codes.
10/20/10
Shearer’s lemma, with applications to counting graph embeddings and the size of intersecting families.
10/25/10
A lower bound on the randomized communication complexity of set disjointness + direct sums in randomized communication complexity
10/27/10
A lower bound on the randomized communication complexity of set disjointness + direct sums in randomized communication complexity (contd.)
11/1/10
The parallel repetition theorem.
11/3/10
Rounds in communication complexity revisited
. N. Nisan, A. Wigderson. Presented by Thach.
11/8/10
On data structures and asymmetric communication complexity
. P. Miltersen, N. Nisan, S. Safra, A. Wigderson. Presented by Johnny.
11/10/10
Logarithmic lower bounds in the cell-probe model
. E. Demaine, M. Pătraşcu. Presented by Kevin.
Kevin’s notes.
11/15/10
An optimal randomised cell probe lower bound for approximate nearest neighbour searching
. A. Chakrabarti, O. Regev. Presented by Mohammad.
11/17/10
The space complexity of approximating the frequency moments
. N. Alon, Y. Matias, M. Szegedy. Presented by Prasang.
11/22/10
A constructive proof of the general Lovasz local lemma
. R. Moser, G. Tardos. Presented by Elisa.
11/24/10
Unbalanced expanders and randomness extractors from parvaresh-vardy codes
. V. Guruswami, C. Umans, S. Vadhan. Presented by Punya.
11/29/10
Pseudorandom generators for regular branching programs.
M. Braverman, A. Rao, R. Raz, A. Yehudayoff. Presented by Widad.
12/1/10
Computational analogues of entropy
. B. Barak, R. Shaltiel, A. Wigderson. Presented by Lukas.
12/6/10
Compression of Samplable Sources
. L. Trevisan, S. Vadhan, D. Zuckerman. Presented by Abhay.
12/8/10
Efficiency 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:
lecture1.tex
11K
Download
preamble.tex
5K
Download
Send questions about this workspace to
Anup Rao
.