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 on. |
Prerequisites |
Mathematical maturity; exposure to advanced undergraduate material in Algorithms, and in Discrete Probability and Combinatorics. More specifically, CSCI 2824 or equivalent, CSCI 3104/5454 or equivalent, familiarity with the notion of algorithm, running time, reduction, turing machine, basic notions of discrete math and probability. 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 |
Alexandra Kolla (alexandra.kolla [at] colorado [dot] edu) 122 ECES [AK]
|
Times |
Tuesday 12:30PM - 13:45PM and Tuesday 12:30PM - 13:45PM |114 ECES |
Office Hours |
Alexandra Kolla - Wednesdays 2:00-3:00PM @ 122 ECES |
| # | Date | Topic | Lecture Slides | Reading Material |
|---|---|---|---|---|
| 1 | Tu August 28 | Introduction to Complexity Theory | Slides | |
| 2 | Th August 30 | Turing machines Review | See these and these lecture notes and Chapter 1 from Arora-Barak | |
| 3 | Tu September 4 | P vs NP, time hierarchy theorems | Slides | See these lecture notes and Chapters 2,3 from Arora-Barak |
| 4 | Th September 6 | Boolean Circuits | Slides | See these lecture notes and Chapter 6 from Arora-Barak | 5 | Tu September 11 | Boolean Circuits,contd. Parallel Computation | Slides | See these lecture notes and Chapter 6 from Arora-Barak |
| 6 | Tu September 13 | Randomized Computation | Slides | See these lecture notes and Chapter 7 from Arora-Barak |
| 7 | Tu September 18 | Polynomial Hierarchy | Slides | See these lecture notes and Chapters 4,5 from Arora-Barak |
| 8 | Tu September 20 | Polynomial Hierarchy and Karp-Lipton-Sipser | See previous lecture | See previous lecture |
| 9 | Tu September 25 | Spece Complexity, NL | Slides | See these lecture notes and Chapter 3 from Arora-Barak | 10 | Th September 27 | NL=co-NL, Undirected Connectivity, Introduction to Eigenvalues | Slides | See these lecture notes |
| 11 | Tu October 2 | More on Spectra | Slides | See these lecture notes | 12 | Th October 4 | Random Walks and Eigenvalues | Slides | See these lecture notes | 13 | Tu October 16 | Zig-Zag Product and Expanders | See these lecture notes | 14 | Th October 18 | Zig-Zag Product and Expanders, contd. | See these lecture notes | 15 | Tu October 23 | L=SL | See these lecture notes | 16 | Th October 25 | Pseudorandom Generators from Exanders. | Slides | See these lecture notes | 17 | Tu October 30 | Valiant-Vazirani. | Slides | See these lecture notes | 18 | Th November 1 | Counting Classes. | Slides | See these lecture notes and Chapter 17 from Arora-Barak | 19 | Tu November 6 | Interactive Proofs. | Slides | See Chapter 13 from these lecture notes and Chapter 8 from Arora-Barak | 20 | Th November 8 | Interactive Proofs, IP=PSPACE Warmup | Slides | See Chapter 14 from these lecture notes and Chapter 8 from Arora-Barak | 21 | Tu November 13 | In-class work group | 22 | Th November 15 | PCPs | See Chapter 11 from Arora-Barak | 23 | Tu November 27 | Intro to Quantum Computing | N/A | See these lecture notes. | 24 | Th November 29 | Intro to Quantum Computing, contd. | N/A | See these lecture notes. | 25 | Tu December 4 | Intro to Quantum Computing, contd. | N/A | See these lecture notes. | 26 | Th December 6 | BQP, Quantum Algorithms | N/A | See these and these lecture notes. |
| Homework # | Due | Homework Solutions |
|---|---|---|
| HW1 | September 13 | Solutions |
| HW2 | September 27 | - |
| HW3 | October 18 | - |
| HW4 | November 8 | - |
| HW5 | December 13 | - |
| HW6 | TBD | - |
| 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. |
|
|
|
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. |