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:
  • 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)
The talk is self-contained and no prior knowledge is assumed.