Course info

Tue-Thu 9:30-11 in  CCB 53 for Spring 2016

Santosh Vempala (Klaus 2222, office hour Tue 11-12) and Anup B. Rao.

We will develop and discuss many of the central tools used in the theory of algorithms and computational complexity.

Course outline: toolkit   Bib file: references.bib

Scribe template: template.tex

 

Selected references available online (See the toolkit file for more)

  • Concentration Inequalities
    • Chernoff’s original paper.
    • McDiarmid’s paper.
    • Hoeffding’s paper.
    • Book Chapter: This has most of the concentration inequalities discussed in class, and some not discussed in class.
  • SVD and Tensor Analysis
    • Book by Kannan and Vempala
  • Random graphs
    • Book by Frieze and Karonski
  • Convex Optimization
    • GLS
  • Lattices
    • Survey by Kannan
  • Boolean functions
    • Book by Ryan O’Donnell
  • Learning/VC-dimension
    • Book by Blum, Hopcroft, Kannan
  • PCP
    • Notes of Guruswami and O’Donnell
    • Survey by Radhakrishnan and Sudan