CS 880 - Advanced Complexity Theory Spring 2006

Course Description

This is an advanced graduate course in complexity theory, bringing you close to the frontier of current research. CS 810 provides you with a sound background on the complexity theory from the 80's and before. CS 880 covers research directions that have been in vogue more recently.

The Spring 2006 edition of CS 880 focuses on expander graphs and their applications in complexity theory. After introducing the concept of an expander and a discussion of the known constructions, we will cover their use in the design of communication networks, error correcting codes, derandomization and space-efficient algorithms for undirected connectivity, the proof of the PCP Theorem and hardness of approximation results, and proof complexity.

Time permitting, we will also look at related concepts like extractors.

Text

There is no required text. Lecture notes will be made available from the course web page.

Prerequisites

Introductory Complexity Theory at the level of CS 810.

Lectures

Currently, three 75-minute time slots are reserved for this course, namely MWF 4:00-5:15pm. The plan is to have an average of two 75-minute lectures per week. Due to conflicts with faculty candidate talks and meetings, which slots will be effectively used may change from week to week. If it works out better, we may end up switching to two different but fixed time slots.

Also, due to a program committee meeting, the first lecture will only be on Monday 1/23.

Course Work

• Scribes (20%). Write lecture notes in groups of two. Someone who missed the class should be able to learn the material from the notes. I expect a draft within 24 hours after the lecture, and the final version a week later. You need to type your notes in LaTeX using the guidelines provided.

• Homework (45%). There will be 3 assignments. You are allowed to discuss the problems in group but you should write out the solutions on your own.

• Project (35%). There will be no exams. Instead, you are expected to work out a project on a topic of your own choosing. The basis should be a recent manuscript or conference paper on computational complexity, say from 2000 or later. Although I will suggest some topics during the 5th week of the semester, I strongly encourage you to start looking for a topic yourself right away. Suitable places to look for inspiration include the Electronic Colloquium on Computational Complexity and the proceedings of the following conferences: STOC, FOCS, Complexity, ICALP, STACS, Random.

  You should discuss your selection with me, and settle down on a topic before Spring break. You can work in groups of two on your project but you should first find a topic on your own, and then look for other people who share your interest. More guidelines will be posted in due time.