The Entropy Soon-To-Be-Method
Or Sheffet
Jan 18, 2012

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:
  • 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.