Network Algorithms and Analysis

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 developing network algorithms and
analyzing network processes

-- Threshold phenomena in random graphs
-- Basics of Percolation theory
-- Concentration of measure and tail bounds
-- Basic 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.

o Diffusion processes in social networks 
o Epidemics
o Design of network structures in networking
o Routing in communication networks
o Distributed systems
 
WHO SHOULD CONSIDER TAKING IT?

Students interested in learning more about advanced algorithms or
pursuing research in any of the following fields would find many
topics of interest.

Algorithms and Theory
Networking
Network Science
Distributed systems

PREREQUISITE

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