name  office  office hour  

Andrej Bogdanov instructor 
abogdano@uottawa.ca  SITE 5068  Fr 2–4 
Complexity theory is the study of problems that are hard for computers. How can we tell whether a problem is truly intractable or a better algorithm is in the cards? We will see some ingenious methods that complexity theorists have developed for this purpose over the past halfcentury.
The hallmark of complexity is a unified view of computation, which is why its insights are relevant throughout computer science (e.g., in cryptography, optimization, machine learning, and quantum computing). We will highlight such connections with other areas in this course.
week  topic  

1  Sep 6  Hardness by counting Shannon’s theorem 

2  Sep 13  Parallel computation Håstad’s theorem 

3  Sep 20  Sequential computation Barrington’s theorem 

4  Sep 27  Sublineartime computation Huang’s theorem 

5  Oct 4  Quantum computation the BennettBernsteinBrassardVazirani theorem 

6  Oct 11  P, NP, and all that the CookLevin theorem 

7  Oct 18  Averagecase hardness and pseudorandom generators the NisanWigderson theorem 

Oct 25  Reading Week  
8  Nov 1  Cryptography, learning, and natural proofs the RazborovRudich barrier 

9  Nov 8  Interactive proofs the BabaiMoran and GoldwasserSipser theorems 

10  Nov 15  Refutations and statistical zeroknowledge Okamoto's theorem 

11  Nov 22  Heuristics and metacomplexity Hirahara’s theorem 

Nov 24  Project presentations (2^{30}4^{30} in SITE 5084) 
You are encouraged to collaborate on the homeworks as long as you write up your own solutions and provide the names of your collaborators. I discourage you from looking up solutions to homework problems online, unless you have exhausted all other resources. If you do so, please provide proper credit and make sure you understand the solution before you write it.
You are not allowed to collaborate on the takehome midterm exam.
You can upload your solutons here or bring them to class.
Notes will be provided for every lecture. Here are some additional references.