CS7880: Special Topics in Theoretical Computer Science

Network Algorithms

Spring 2016

Instructor: Rajmohan Rajaraman
Class Meeting Times: TuF 9:50-11:30 AM
                                     Ryder Hall 155
Office Hours: Tu 5:00-6:00 PM 240 WVH
                        and after class


Tentative Course Schedule

Piazza Link Piazza Link Piazza Link Piazza Link

Course Description   Textbook Prerequisites   Grading Final Project

Course Description

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

Network Processes

Random walks and Markov chains
Small-world phenomena
Consensus networks
Information spreading protocols

Network Analysis

Processing of large-scale networks
Graph clustering
Graph sparsification
Graph streams

Network Optimization

Approximation algorithms for network design
Multicommodity flow
Steiner network design
Linear programming (LP) based methods: rounding, primal-dual
Semidefinite programming (SDP) methods
Multiplicative weights method

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

Analysis of large-scale graph and network data
Diffusion in social networks
Epidemics
Design of graph structures in networking
Routing in communication networks
Distributed systems

Textbook

There is no required textbook for the course. We will draw material from research papers and books listed in the schedule page. Here are some books and course notes that will be referenced for the course.

Jon Kelner, An Algorithmist's Toolkit, MIT
Dan Spielman, Spectral Graph Theory, Yale
David Easley and Jon Kleinberg, Networks, Crowds, and Markets, Cambridge U. Press, 2010
Williamson and Shmoys, The Design of Approximation Algorithms, Cambridge U. Press
Noga Alon and Joel Spencer, The Probabilistic Method, Wiley
Luca Trevisan, Graph Partitioning and Expanders, Stanford
Michael Mitzenmacher and Eli Upfal, Probability and Computing

Prerequisites

The prerequisite for this course is a graduate course or senior undergraduate course in algorithms. The student must be familiar with asymptotic notation, greedy algorithms, dynamic programming, graph algorithms (e.g., minimum spanning trees, shortest paths), NP-completeness.

Grading

Since this is an advanced course, we will generally avoid stress-inducing activities such as tests. The course grade will be based on 2-3 problem sets (worth 30\%), class participation (20\%), and a project (50\%).

Since this is expected to be a small class, I am hoping that the lectures are interactive, with discussions leading toward improved understanding of technical material, and identification of research directions. Every student is expected to scribe one week's worth of lectures. The grade for class participation will be determined by the extent and impact of the student's participation in class discussions and their contributions to the scribe notes.

Project

Students will be required to do a research project in the second half of the course. The research project should focus on an algorithmic problem, either a fundamental theoretical problem or one well-motivated by an application. If the student is already working on a research problem relevant to the course, then a well-defined piece of the problem
with specific goals can be chosen as a research project.

Students pursuing research (or interested in pursuing research) in algorithmic application areas are strongly encouraged to formulate problems on their own for the research project. Problem and model formulation is as important a component of research as problem-solving and will be emphasized throughout the course. The research
project could also involve a substantial implementation component.

The project topics will be decided by the halfway point of the semester (by the end of February). The completion of the project will have two deliverables -- a paper and a presentation in the last 2 weeks of the semester.