About the Courses

Information Theory in Computer Science
(Madhu Sudan)

The aim of this course is to introduce the tools of Information Theory that end up seeing applications in the theory of Computer Science.

Information Theory originated in the seminal work of Shannon (1948) that attempted to formalize and quantify communication. This theory was mostly ignored by theoretical computer science till the 1990s when tools and concepts from Information Theory started to play a central role in powerful results in the field. Notable examples include the Parallel Repetition Theorem of Raz (1994), the development of the Information Complexity measure as a means of understanding Communication Complexity (2001). Today Information Theoretic measures and tools influence many aspects of CS theory including analysis of streaming algorithms, differential privacy and game theory.

This course will introduce the basic concepts in information theory and then sample topics of interest to CS theory where information theoretic tools play a central role. Potential topics include Communication Complexity, Parallel Repetition Theorem, and Polar Coding.

The course will be a compression of a course being offered currently at Harvard. See http://madhu.seas.harvard.edu/courses/Spring2019 for more information.

Spectral Graph Theory
(Luca Trevisan)

This course is about applications of linear algebra to graph theory and graph algorithms. We will see that, given a graph, we can associate a matrix to it and we can discover important properties of the graph, and we can design very effective graph algorithms, by studying the eigenvalues and eigenvectors of this matrix.

We will see worst-case and average-analysis of spectral clustering algorithms, which find clusters in graphs, and we will see how to use spectral (that is, linear-algebraic) techniques to find planted cliques in random graphs.

We will then see how graph theory gives back to linear algebra, and we will analyze nearly-linear time algorithms for solving a certain class of linear systems, by associating a graph to the matrix defining the linear system, and applying graph-theoretic ideas.