Text: Arora/Barak, Complexity Theory (due to appear in print in late Spring 2009)

Syllabus

Arora / Barak - Complexity Theory

Nilli - Tight estimates for eigenvalues of regular graphs

Lovasz - Random walks on Graphs : A Survey

Notes on the Margulis Construction (Linial & Wigderson lecture notes)

Reingold - Undirected Connectivity in Log-Space

Proof of Leftover Hash Lemma

Quasirandom Notes 1

Quasirandom Notes 4

David MacKay's Short Course in Information Theory

Radhakrisnan - Entropy and Counting

Friedgut - Hypergraphs, Entropy, and Inequalities

Kahn, Entropy, independent sets and antichains -- A new approach to Dedekind's problem.pdf

---

Homework 1: PDF / TeX
Homework 1 Solutions: PDF / TeX

Homework 2: PDF / TeX
Homework 2 Solutions: PDF / TeX

Homework 3: PDF / TeX
Homework 3 Solutions: PDF / TeX

Homework 4: PDF / TeX
Homework 4 Solutions: PDF / TeX

---

Back to my homepage.