Course Information
Instructor: Zachary Friggstad
Contact Information: click here
Lecture: Tuesday & Thursday 12:30-1:50pm in CAB 365
Office Hours: TBD
Outline
You are probably familiar with the famous P vs. NP problem. It is, without a doubt, the most famous open problem in complexity theory and is recognized as one of the most important unsolved problems in all of mathematics.
Looking beyond, this important problem is just one of many interesting discussions in the theory of computation! Computational complexity studies various computational models, how they relate, and their limitations. What sort of problems can we solve if we allow exponential-time computations? Are there interesting problems that cannot even be solved in exponential time? What if we have severely limited space requirements (eg. logarithmic work space)? How do randomized algorithms help? What problems cannot be solved by any classical algorithm in any amount of time?
These are fairly classic topics in compuational complexity, but there are more! Fine-grained scrutiny sheds insight into cryptography, explains some difficulties in designing approximation algorithms, describes how to construct a pseudorandom number generator to look like a true random number generator, reveals a spectrum of complexity classes lying between NP and PSPACE, to name a few exciting directions.
Background
Students are expected to have a background in algorithms at the level of CMPUT 304. Exposure to Turing machines in a course like CMPUT 474 will help with the start of the course, but is not strictly necessary.
Most results in this course are justified with a proof. Many proofs are just simple observations applied in clever ways, but some involve more intricate arguments especially in the second half of the class. Students are expected to provide proofs in assignments, though they will not be as challenging as some proofs seen in class. Concepts from discrete math, random variables, and linear algebra will be used from time to time.
References
No textbook is required. However, most lectures will draw from Computational Complexity: A Modern Approach by Arora and Barak. You can access an electronic copy of the book through our library. Note there is a full .pdf draft of a pre-publication version that you can find online. I suggest you avoid that version, the chapter numbering is different and it contains more errors and typos than the published version.
Further resources can be found at the bottom of this course page .
Topics
A list of core topics that will be covered (to varying degrees) follows.
- Turing machines and universal simulations.
- Basic space and time classes and some relationships between classes. Nondeterministic complexity classes. Completeness and reductions in some popular classes.
- The diagonalization technique. Oracles.
- Arithmetic and polynomial hierarchy.
- Circuit complexity.
- Randomized computation and complexity classes.
- Interactive proofs. Arthur-Merlin interactions. PSPACE vs. IP.
- Cryptography. One-way functions, pseudorandom generators, and zero-knowledge proofs.
-
Basic construction of probabilistically checkable proof systems.
Roughly speaking, if you allow randomization with a verifier for a problem in NP, then we really only need to look at \(O(1)\) bits of the proof to decide with good probability if we should accept the proof. But only if the proof is encoded in a very careful way!
Following these core topics are more advanced topics. The precise topics are not yet decided, but a list of possibilities is below. We surely cannot cover all, we will decide as we go.
- Derandomization. Building pseudorandom number generators to fool efficient algorithms.
- Random walks in graphs and some spectral graph theory.
- Further into probabilistically-checkable proof systems: constructions using much fewer random bits.
- The complexity of counting.
- Further into techniques for proving some circuit lower bounds.
- Communication complexity and its surprising applications.
Grading
Assignments - 60%
There will be 5 assignments in total, each worth 12%. You will have 2 weeks to complete each assignment. Each assignment will be due on a Thursday and must be handed in at the start of the lecture.
Scribe Notes - 15%
Students will take turns recording notes from each lecture and typesetting them in LaTeX. Any details that were omitted or glossed over must be filled in. The notes will be due exactly one week after the start of the lecture (i.e. at 1pm 7 days later). These will be posted on this page for others to reference. I will provide a .tex template and notes from the first lecture.
Some details during the lecture might be glossed over. You should fill out these missing details, the goal of the notes is to be a self-contained description of the lecture topic. I might edit the notes, but I will check with you regarding any edits I make before posting. The grades here are largely based on:
- Clarity: Does the writeup demonstrate good style? Is it easy to read (relatively speaking, of course, some topics are technical).
- Comprehensiveness: Were all the lecture topics covered? Are all proofs supplied?
- Correctness: Are the details correct? Is the notation properly introduced and used in a consistent manner?
Take-Home Exam - 25%
A take-home exam near the end of the term. You will have a few days to complete it. These must be completed individually, no collaboration. The exam can be found here and is also by a link from the Assignments section.
Lecture Notes
You can download the .tex template here (.pdf version and the figure).
On a lab machine, you can compile the document with pdflatex <filename> (you can omit .tex from the filename). Run it twice to fix the "undefined reference" messages.
A quick LaTeX tutorial.
References: AB - Arora & Barak
| Lecture # | Date | Topic | Scribe | Additional Reference |
|---|---|---|---|---|
| 1 | Jan 8 | Introduction and Turing Machines | Zac Friggstad | AB Chapter 1 |
| 2 | Jan 10 | Undecidability and Hierarchy Theorems | Zac Friggstad | AB Chapter 1 and 3.1 |
| 3 | Jan 15 | Nondeterminism and the Class NP | Joshua Teitz | AB Chapter 2 |
| 4 | Jan 17 | NP-Completeness and the Cook/Levin Theorem | Haozhou Pang | AB Chapter 2 |
| 5 | Jan 22 | Ladner's Theorem and Oracles | Jason Cannon | AB Chapters 2 and 3 |
| 6 | Jan 24 | Space Complexity | Laura Petrich | AB Chapter 4 |
| 7 | Jan 29 | The Polynomial Hierarchy and Alternating Turing Machines | Zach Goldthorpe | AB Chapter 5 |
| 8 | Jan 31 | Time/Space Tradeoffs for SAT, and Circuits | Noah Weninger |
AB Chapters 5 and 6 Notes from Paul Beame's Course |
| 9 | Feb 5 | Circuits and Randomized Algorithms | Joseph Meleshko |
AB Chapter 6 Notes from Nick Harvey's Course |
| 10 | Feb 7 | Randomized Complexity | Jacob Garber | AB Chapter 7 |
| 11 | Feb 12 | BPP and Interactive Proofs | Yue Gao | AB Chapter 7 and 8.1 |
| 12 | Feb 14 | Interactive Proofs using Public Coins | Ramin Mousavi | AB Chapter 8.2 |
| 13 | Feb 26 | IP = PSPACE | Tim Put |
AB Chapter 8.3 Notes from Jonathan Katz' Course |
| 14 | Feb 28 | Probabilistically Checkable Proofs (Intro) | Haozhou Pang | AB Chapter 11 |
| 15 | Mar 5 | A PCP Verifier for NP With Exponential Proof Size | Zachary Friggstad | AB Chapter 11 |
| 16 | Mar 7 | Cryptography Introduction | Jason Cannon | AB Chapter 9 |
| 17 | Mar 12 | Cryptography | Joseph Meleshko | AB Chapter 9 |
| 18 | Mar 14 | Cryptography & Spectral Graph Theory | Yue Gao | AB Chapter 9, Parts of 21.1, 21.2 |
| 19 | Mar 19 | Expander Graphs | Noah Weninger | AB Chapter 21.3 and Example 22.7 |
| 20 | Mar 21 | Constructing Expander Graphs | Ramin Mousavi | AB Chapter 21.3 |
| 21 | Mar 26 | The PCP Theorem: Part I | Zachary Friggstad |
AB Chapter 22.1, 22.2, and 22.A Gap Amplification in PCPs Using Lazy Random Walks |
| 21 | Mar 26 | The PCP Theorem: Part II | Zachary Friggstad |
AB Chapter 22.2 Gap Amplification in PCPs Using Lazy Random Walks |
| 23 | Apr 2 | Zach Goldthorpe | ||
| 24 | Apr 4 | Joshua Teitz | ||
| 25 | Apr 9 | Tim Put |
Assignments
Each marked assignment is due on a Thursday and must be handed in by the start of the lecture on the due date.
Suggestions
Messy and rambling solutions are difficult to read, it may be hard to assign full marks even if the solution is ultimately correct. A good solution is precise, neat, and to the point.
Typesetting your assignment solutions in LaTeX is strongly encouraged, especially if your writing is messy. A paper submission is still required.
Do not stumble around with a longwinded answer that does not solve the problem. If you cannot solve the problem entirely, get as far as you can and write it up nicely. You may get partial credit for keen observations.
| Assignment # | Description | Due date | Solution |
|---|---|---|---|
| 1 | Assignment #1 | Feb 7 | Solution, Part 1 TM |
| 2 | Assignment #2 | Feb 26 | Solution |
| 3 | Assignment #3 | Mar 7 | Solution |
| 4 | Assignment #4 | Mar 21 | Solution |
| 5 | Assignment #5 | Apr 20 | |
| Final | Take Home Exam | Apr 26 |
External Resources
Book
As stated earlier, we will closely follow Computational Complexity: A Modern Approach by Arora and Barak
Related Courses
Here are similar courses complete with scribe notes and/or lecture videos. The topics may vary from ours, especially in the latter half of these courses.
Course Policies
Collaboration Policy
We are adopting the consultation model for colaboration in the assignments only. In particular, it is OK to have high-level verbal discussions about problems in the assignments with other students but absolutely no written material should be produced or shared in these meetings. You must write up the entire solution yourself. Reproducing another student's written work in whole or in part is not permitted!
This does not apply to the take-home exam. The take-home exam must be completed entirely on your own with no consultation from other students.
Late Assignments
I will not accept late submissions. In extreme cases, the weight of an assignment may be transferred to other work required over the term (subject to the instructor's approval).
The take-home exam must be completed, so a student who cannot complete this work on time due to extenuating circumstances can apply for an extension. Deferal of term work is a privilege and not a right; there is no guarantee a deferral will be granted. Misrepresentation of the facts to gain a deferral is a serious breach of the Code of Student Behavior.
Academic Integrity
The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behaviour (online at www.governance.ualberta.ca) and avoid any behaviour which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University.
All forms of dishonesty are unacceptable at the University. Any offence will be reported to the Associate Dean of Science who will determine the disciplinary action to be taken. Cheating, plagiarism and misrepresentation of facts are serious offences. Anyone who engages in these practices will receive at minimum a grade of zero for the exam or paper in question and no opportunity will be given to replace the grade or redistribute the weights. Policy about course outlines can be found in 23.4(2) of the University Calendar.
Disclaimer: Any typographical errors in this Course Outline are subject to change and will be announced in class.