Information Theoretic Techniques in Theoretical Computer Science II
Presenter
December 8, 2011
Keywords:
- information theory
- combinatorial optimization
- applied combinatorics
- probability theory
- conditional probability
MSC:
- 68W25
- 68W40
- 68Wxx
- 68P30
- 68P20
- 68P25
- 68Pxx
- 94A24
- 94A20
- 94A17
- 94Axx
Abstract
We will give some recent examples of applications of information theoretic techniques in theoretical computer science, covering such topics as communication complexity, locally decodable codes, dimension reduction in \ell_1, and more. No prior knowledge will be assumed.