The Entropy Soon-To-Be-Method

Or Sheffet

Jan 18, 2012

ABSTRACT:

In the last couple of decades, several combinatorial bounds and algorithmic results were obtained using techniques that are derived from Information Theory. In this talk we will survey a few of them, demonstrating just how widely applicable such techniques are. A tentative list of topics:

In the last couple of decades, several combinatorial bounds and algorithmic results were obtained using techniques that are derived from Information Theory. In this talk we will survey a few of them, demonstrating just how widely applicable such techniques are. A tentative list of topics:

- Bounding the number of cliques in a graph
- Bregman's theorem, (ref: An entropy proof of Bregman's theorem, Radhakrishnan J)
- Graph entropy (ref: Graph entropy: a survey, Simonyi G and Anup Rao's "Information theory in computer science" course notes: https://catalyst.uw.edu/workspace/anuprao/15415/86751)
- Kahn and Kim's sorting algorithm (ref: Entropy and sorting, Kahn J. and Kim J.H)
- The recent LLL algorithm (ref: A constructive proof of the LovĂˇsz local lemma, Moser R.A)