CS579: Computational Complexity

Spring 2017

UNIVERSITY OF ILLINOIS, URBANA - CHAMPAIGN

META

Subject

A main objective of theoretical computer science is to understand the amount of resources needed to solve computational problems. While the design and analysis of algorithms puts upper bounds on such amounts, computational complexity theory is mostly concerned with lower bounds; In this class, we will be largely interested in infeasible problems, that is computational problems that require impossibly large resources to be solved, even on instances of moderate size. It is very hard to show that a particular problem is infeasible, and in fact for a lot of interesting problems the question of their feasibility is still open. Another direction this class studies is the relations between different computational problems and between different “modes” of computation. For example what is the relative power of algorithms using randomness and deterministic algorithms, what is the relation between worst-case and average-case complexity, how easier can we make an optimization problem if we only look for approximate solutions, and so onA tentative syllabus can be found here

Prerequisites

Mathematical maturity; exposure to advanced undergraduate material in Algorithms, and in Discrete Probability and Combinatorics. More specifically, CS 374, and MATH 461 or STAT 400 or equivalent are required.

If you have not taken those classes but believe that your background is close to being sufficient, please make sure you have filled up any potential gaps by the end of the second week of classes. You can refer to the standard algorithms and probability textbooks for the classes above as supplementary material.

If you are not sure whether your background suffices, please see the instructor. The course is designed for graduate students but may be suitable for advanced undergraduates. Undergraduate students who are interested in taking the course are advised to consult with the instructor before registering.

Instructor

Teaching Assistant

Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK]

Spencer Gordon (slgordo2 [at] illinois [dot] edu) 3111 [SG]

 

Times

Wednesday 11:00AM - 12:15PM and Friday 11:00AM - 12:15PM | 1109 SC

Office Hours

Alexandra Kolla - Wednesdays 4:00PM @ 3222 SC

Spencer Gordon - Tuesdays 2:00PM @ Siebel 3rd Floor Lounge

 

 

SCHEDULE

# Date Topic Lecture Slides Reading Material
1 W January 18 Introduction to Complexity Theory Slides  
2 F January 20 P vs NP, time hierarchy theorems Slides See these lecture notes and Chapters 2,3 from Arora-Barak
3 W January 25 Time Hierarchy Thoerems cont., Space Complexity Slides See Chapter 4 from Arora-Barak
4 F January 27 NL=coNL, Polynomial Hierarchy Slides See these lecture notes and Chapters 4,5 from Arora-Barak
5 W February 1 Polynomial Hierarchy See previous lecture See previous lecture
6 F February 3 Boolean Circuits Slides See these lecture notes and Chapter 6 from Arora-Barak
7 W February 8 Randomized Computation Slides See these lecture notes and Chapter 7 from Arora-Barak
7 F February 10 Valiant-Vazirani Slides See these lecture notes
8 W February 15 Counting Problems Slides See these lecture notes and Chapter 17 from Arora-Barak
9 F February 17 Interactive Proofs Slides See Chapter 8 from Arora-Barak
10 W February 22 IP=PSPACE Warmup Slides 1 and Slides 2 See Luca's notes and Chapter 14 from Arora-Barak
11 F February 24 Goldwasser-Sipser Set Lower Bound, MIP N/A See Chapter 14 from Arora-Barak
12 W March 1 Undirected Connectivity, Introduction to Eigenvalues Slides See these lecture notes
13 F March 3 More on Eigenvalues N/A See these lecture notes
14 W March 8 No class.
15 F March 10 Eigenvalues and Random Walks, UCONN in RL Slides See these lecture notes
16 W March 15 Quasi-Random Properties of Expanders, PRGs Slides See these lecture notes
17 F March 17 Linear Algebra Review N/A N/A
18 W March 22 Zig-Zag Product and Expanders N/A See these lecture notes
19 F March 24 Zig-Zag Product and Expanders, cont. N/A See these lecture notes
20 W March 29 More on the Zig-Zag Product N/A See these lecture notes
21 F March 31 More on the Zig-Zag Product, cont. N/A See these lecture notes
22 W April 5 L=SL N/A See these lecture notes and this paper
23 F April 7 Intro to Quantum Computing N/A See these lecture notes.

 

 

 

Homework # Due Homework Solutions
HW1 February 3 before the end of class Solutions
HW2 February 17 before the end of class -
HW3 March 3 before the end of class -
HW4 March 29 before the end of class -
HW5 April 14 before the end of class -
HW6 May 3 before the end of class -

COURSEWORK and GRADING POLICIES


Homework
There will be a total of 5-6 homeworks.
They can be turned in in groups of up to 3 students. All students in each group get the same grade.

Please do not forget to cite your sources (you will get a zero if you use material from elsewhere and do not cite the source!)

 

 

Project
There will be a final project. More details to come.
Here is a list of potential project ideas: Project Ideas.
We can provide references to help you get started looking into any of these projects. You may also come up with a project idea of your own.
Grading
70% homeworks and 30% exam/final project. Extra points may be given for class participation at various occasions.

 

TENTATIVE SYLLABUS

Part 1: "Classical Complexity Theory" (about 5 weeks)

We will start with "basic" and "classical" material about time, space, P versus NP, polynomial hierarchy, circuit complexity and so on, including moderately modern and advanced material, such as the power of randomized algorithms, the complexity of counting problems, the average-case complexity of problems, and interactive proofs. 

Part 2: "Spectral Techniques for Complexity Theory " (about 4 weeks)

 

- We will learn techniques from spectral graph theory and apply them to several key complexity theory results such as expander graphs, the Unique Games Conjecture, pseudorandom generators, and Reingold's L=SL result. 

 

Part 3: "Quantum Computing" (about 2 weeks)

 

We will focus on quantum complexity theory.

Part 4 (tentative):  "Final Presentations" (remaining time)

Depending on attendance.

   

 

READING MATERIAL

 

 

Top