Subject 
A main objective of theoretical computer science is to understand the amount of re sources 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 worstcase and averagecase complexity, how easier can we make an optimization problem if we only look for approximate solutions, and so on. A 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 is required and MATH 461 or STAT 400 is recommended. 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 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 
Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK]

Times 
Tuesday 15:30PM  16:45PM and Thursday 15:30PM  16:45PM  1131 SC 
Office Hours 
TBD. 
#  Date  Topic  Lecture Slides  Reading Material 

1  T January 19  Introduction to Complexity Theory  Slides  
2  R January 21  P vs. NP, Deterministic Hierarchy Theorems  Slides  See these lecture notes and Chapters 2,3 from AroraBarak 
3  T January 26  Space Complexity  Slides  See Chapter 4 from AroraBarak 
4  R January 28  Nl=coNL, Polynomial Hierarchy  Slides  See these lecture notes and Chapters 4,5 from AroraBarak 
5  T February 2  Boolean Circuits  Slides  See these lecture notes and Chapter 6 from AroraBarak 
6  R February 4  Randomized Computation  Slides  See these lecture notes and Chapter 7 from AroraBarak 
7  T February 9  ValiantVairani  Slides  See these lecture notes 
8  R February 11  Counting Problems  Slides  See these lecture notes and Chapter 17 from AroraBarak 
9  T February 16  Interactive Proofs  Slides  See Chapter 8 from AroraBarak 
10  R February 18  IP=PSPACE Warmup  Slides 1 and Slides 2  See Chapter 14 from Luca's notes 
11  T March 1  Undirected Connectivity, Introduction to Eigenvalues  Slides  See these lecture notes 
12  R March 3  More on Eigenvalues  See these lecture notes  
13  T March 8  Eigenvalues and Random Walks, UCONN in RL  Slides  See these lecture notes 
14  R March 10  QuasiRandom Properties of Expanders, PRGs  Slides  See these lecture notes 
15  T March 15  More on PRGs  
16  R March 17  ZigZag Product and Expanders  See these lecture notes  
17  T March 29  More on the ZigZag Product  See these lecture notes  
18  R March 31  L=SL and Introduction to Quantum Computing  See these lecture notes and this paper  
19  T April 5  Quantum Computing Basics  See these lecture notes  
20  R April 7  No class  
21  T April 12  Nocloning theorem and Quantum Teleportation  See these lecture notes  
22  R April 14  Nocloning theorem and Quantum Teleportation  
23  T April 19  DeutschJozsa Algorithm  See these lecture notes  
24  R April 21  No class  
25  T April 26  Final Presentation: Yifang Zhang  slides  
26  R April 28  Final Presentation: Tom Bogue  notes  
27  T May 3  Final Presentation: Charles Carson  slides  
28  
29 
Homework #  Due  Homework Solutions 

Feb 16 by midnight  Solution of Question 4(b)  
HW2  March 29 by midnight 
HW3  May 1 by midnight 
Homework 

There will be a total of 3 homeworks. 
Please do not forget to cite your sources (you will get zero grade if you use material from elsewhere and do not cite the source!) 
Exams 

There will be a take home final exam OR a final project (depending on attendance). 
Grading 

70% homeworks and 30% final. Extra points may be given for class participation at various occasions. 

Part 1: "Classical" Complexity Theory. (Weeks 16) 
We will start with "basic" and "classical" material about time, space, P versus NP, polynomial hierarchy and so on, including moderately modern and advanced material, such as the power of randomized algorithm, the complexity of counting problems, the averagecase complexity of problems, random walks, expanders and L vs. SL. 
Part 2: "Advanced" topics. (Weeks 710)

In the second part, we will focus on more research oriented material, to be chosen among: (i) PCP, hardness of approximation and the Unique Games Conjecture; (ii) lower bounds for proofs and circuits; (iii) derandomization and averagecase complexity; (iv) quantum complexity theory. 
Part 3 (tentative):

Final Presentations from students. 