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 worst-case and average-case 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 Arora-Barak |
| 3 | T January 26 | Space Complexity | Slides | See Chapter 4 from Arora-Barak |
| 4 | R January 28 | Nl=coNL, Polynomial Hierarchy | Slides | See these lecture notes and Chapters 4,5 from Arora-Barak |
| 5 | T February 2 | Boolean Circuits | Slides | See these lecture notes and Chapter 6 from Arora-Barak |
| 6 | R February 4 | Randomized Computation | Slides | See these lecture notes and Chapter 7 from Arora-Barak |
| 7 | T February 9 | Valiant-Vairani | Slides | See these lecture notes |
| 8 | R February 11 | Counting Problems | Slides | See these lecture notes and Chapter 17 from Arora-Barak |
| 9 | T February 16 | Interactive Proofs | Slides | See Chapter 8 from Arora-Barak |
| 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 | Quasi-Random Properties of Expanders, PRGs | Slides | See these lecture notes |
| 15 | T March 15 | More on PRGs | ||
| 16 | R March 17 | Zig-Zag Product and Expanders | See these lecture notes | |
| 17 | T March 29 | More on the Zig-Zag 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 | No-cloning theorem and Quantum Teleportation | See these lecture notes | |
| 22 | R April 14 | No-cloning theorem and Quantum Teleportation | ||
| 23 | T April 19 | Deutsch-Jozsa 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 1-6) |
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 average-case complexity of problems, random walks, expanders and L vs. SL. |
|
Part 2: "Advanced" topics. (Weeks 7-10)
|
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 average-case complexity; (iv) quantum complexity theory. |
|
Part 3 (tentative):
|
Final Presentations from students. |