CSI 5138: Computational Complexity

University of Ottawa, Fall 2023

Recent Announcements

• 06 Dec Please submit your project report using the usual link.
• 20 Nov Please fill in the course evaluation.
• 10 Oct Here is information about the project.

Teaching Staff

name	email	office	office hour
Andrej Bogdanov instructor	abogdano@uottawa.ca	SITE 5068	Fr 2–4

Course Description

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 half-century.

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.

Schedule

	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	Sublinear-time computation Huang’s theorem
5	Oct 4	Quantum computation the Bennett-Bernstein-Brassard-Vazirani theorem
6	Oct 11	P, NP, and all that the Cook-Levin theorem
7	Oct 18	Average-case hardness and pseudorandom generators the Nisan-Wigderson theorem
	Oct 25	Reading Week
8	Nov 1	Cryptography, learning, and natural proofs the Razborov-Rudich barrier
9	Nov 8	Interactive proofs the Babai-Moran and Goldwasser-Sipser theorems
10	Nov 15	Refutations and statistical zero-knowledge Okamoto's theorem
11	Nov 22	Heuristics and meta-complexity Hirahara’s theorem
	Nov 24	Project presentations (230-430 in SITE 5-084)

Homeworks

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 take-home midterm exam.

• Homework 1 | out Sep 20 | in Sep 27 | solutions
• Homework 2 | out Oct 4 | in Oct 11 | solutions
• Midterm exam | out Oct 18 | in Oct 25 | solutions
• Homework 3 | out Nov 8 | in Nov 15 | solutions

You can upload your solutons here or bring them to class.

Course Information

• Lectures Wednesdays 2.30-5.20 in Simard (SMD) 221.
• Prerequisites There are no formal prerequisites, but knowledge of algorithms (at the level of CSI 3105) and computational models (at the level of CSI 3104) is helpful. Familiarity with discrete mathematics and basic probability will be assumed. If you are not sure that your background is adequate please talk to me.
• Grading Your grade will be determined from three homeworks (30%), a take-home midterm exam (30%), and a final project report and presentation (40%).
• Final project For your final project you will be expected to do a small research project or some independent reading. More information including potential project topics will be provided after the midterm. Projects can be done individually or in pairs. The project grade be be based on your in-class project presentation (on Nov 29) and your project report (to be submitted by Dec 8).
• Discussion You can use this piazza forum for homework collaboration and other discussions.

References

Notes will be provided for every lecture. Here are some additional references.

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2008.
• Oded Goldreich. Computational complexity: A conceptual perspective. Cambridge University Press, 2008.
• Stasys Jukna. Boolean function complexity: Advances and frontiers. Springer-Verlag, 2012.
• Avi Wigderson. Mathematics and computation. Princeton University Press, 2019.