This course covers advanced techniques in network algorithms and analysis.  The topics covered in the course can be broadly classified into three categories.  This is an amibitious list, and the actual topics covered will vary depending on time constraints and the interests of the students taking the course.

Spectral graph theory

Graph Laplacians and their eigenvalues

Random walks, Markov chains, and mixing times

Isoperimetric inequalities

Expanders and their applications

Probabilistic techniques for network algorithms and analyzing network processes

Threshold phenomena in random graphs

Basics of Percolation theory

Concentration of measure and tail bounds

Randomization in distributed network algorithms

Approximation algorithms for network optimization

Basic combinatorial techniques

Linear programming (LP) based methods: rounding, primal-dual

Semi-definite programming (SDP) based methods

Multiplicative weights method

WHAT WOULD BE EXPECTED OF THE STUDENTS?

Since this is a special topics course, we will not have any stress-inducing components like exams.  The deliverables will include 2-3 problem sets, a research/survey project, and scribing lecture notes for one week's classes.  The aim of the project would be to study a problem domain in greater depth, potentially leading to to a publication with some more effort outside the course.

APPLICATIONS

While the course will have a theoretical focus, we will draw from several applications involving networks, including the following. Also, the final projects can be anywhere on the theory-experiments spectrum.

Diffusion processes in social networks

Epidemics

Design of graph structures in networking

Routing in communication networks

Distributed systems

WHO SHOULD CONSIDER TAKING IT?

Students interested in learning more about advanced algorithms or

pursuing research in Algorithms/Theory, Networking, Network Science, Distributed Systems, or related areas would find many topics of interest.

PREREQUISITE

A graduate-level or senior undergraduate level course in algorithms, and mathematical maturity.

GRADING

Grades will be based on problem sets (30%), a term project (60%), and class participation (10%).

Instructor:

Rajmohan Rajaraman

Class:

TF 1:35-3:15

227 RI

Office Hours:

T 3:30-4:30

F 5:00-6:00

Piazza