CS 281 Computability and Complexity

Professor   Alexander Sherstov
Email my last name @cs.ucla.edu
Quarter Fall 2020
Room & Time TR 2–3:50pm (Zoom)
Office Hours TR 3:50–4:20pm (Zoom)
Webpage http://www.cs.ucla.edu/~sherstov/teaching/2020-fall
Textbook S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.


Computers have become faster over the decades. Computations that were infeasible fifty years ago now take a split second. However, many natural and practically significant computational problems will always remain off limits. Computational complexity is a branch of discrete mathematics that studies the fundamental limitations to efficient computation. A variety of resources other than time can be used to quantify efficiency, such as memory and randomness. Computational complexity theory studies these resources in a unified, clean, and abstract way.

This graduate course will cover many of the field's celebrated discoveries and outline current research frontiers. Tentative topics include NP-completeness, diagonalization, oracle computations, space complexity, Turing machines with alternating quantifies, Boolean circuits and circuit lower bounds, randomized computation, interactive proofs, derandomization, pseudorandom constructions, and probabilistically checkable proofs. This course is mathematically demanding, making mathematical maturity an important prerequisite. Another prerequisite is CS 181 or an equivalent undergraduate course on the theory of computation.


Scribe notes. Scribe notes are a complete and polished write-up of a given lecture, with bibliographic references and technical details carefully filled in. Every student should expect to scribe once or twice, depending on class size. At the beginning of every lecture, I will ask for a volunteer to be the scribe for the day. Please do not volunteer if there is a chance that you will drop the course before you submit your scribe notes. Preparing the scribe notes will help you internalize the material at a new level, by thinking through the significance of the material and by completing every proof outline in class to a rigorous proof. Please typeset your scribe notes in LaTeX using the instructions and template below. You have one week to prepare the scribe notes. More precisely, the scribe notes for a Tuesday lecture are due at 2pm the following Tuesday, and analogously the scribe notes for a Thursday lecture are due at 2pm the following Thursday (regardless of any intervening holidays). Please email me your .pdf file and the source files (.tex and .bib, as well as figure files if any). Please email me your files as a single ZIP archive; do not use compressed formats other than ZIP.

Instructions Template

Midterm and final. There will be two exams, a midterm and a cumulative final exam. The exams will require you to apply the ideas and proof techniques from the lectures in a creative way, to solve new problems. An excellent way to prepare for the exams is to carefully understand every proof presented in class and solve as many exercises in the textbook as you can. Please see below for important policies.

Participation. Attendance and class participation are essential for success in this course. Please do your best to attend every lecture and always be on time. I emphatically welcome questions during lecture and any other input from you—your active participation in this course will enhance your own learning experience and that of your fellow students.

Points Grade
≥ 97 A+
94–96 A
90–93 A−
87–89 B+
84–86 B
80–83 B−
77–79 C+
74–76 C
70–73 C−
≤ 69 F
Activity Points
Scribe notes 30
Midterm 30
Final 30
Participation 10

The tables above indicate the number of points assigned to each component of the course, as well as the grading scale used to convert cumulative points to course grades. The grades D+, D, and D− are not assigned to graduate students at UCLA.

Course Schedule

The following table gives the sequence of topics that we will cover, along with the number of hours of instruction devoted to each topic and the corresponding chapter(s) of the Arora-Barak text.

Topic Lecture Hours Chapter
Deterministic computation 3 1
Nondeterminism 4 2
Diagonalization 5 3
Space complexity 4 4
Polynomial hierarchy 2 5
Randomness 3 7
Boolean circuits 4 6, 14
Interactive proofs 2.5 8
Counting 4 17
Hardness of approximation 4 11


Academic honesty. The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating will have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.

Attendance. Although not a formal component of the course grade, attendance is essential for success in this course. I emphatically welcome questions during lecture and any other input from you—your active participation in this course will enhance your own learning experience and that of your fellow students.

Late policy. Late work will not be accepted, resulting in zero credit for the corresponding assignment.

Zoom use. Due to the COVID-19 pandemic, the lectures and office hours will take place via Zoom. The Zoom links for lectures and office hours can be accessed from the CCLE webpage for this course, by clicking on "Zoom Video Conferencing" in the navigation panel on the left. For security reasons, these Zoom links and passwords are only for use by students registered for CS 281, and must not be shared. Please be advised that the lectures will be recorded and posted in video format on CCLE.