CS 281 Computability and Complexity

Professor   Alexander Sherstov
Email my last name @cs.ucla.edu
Quarter Spring 2017
Room & Time MW 2–3:50pm, Boelter 5280
Office Hours MW 1:30–2pm, Boelter 3731J
Webpage http://www.cs.ucla.edu/~sherstov/teaching/2017-spring
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 for one or two lectures, depending on class size. At the beginning of every lecture, I will ask for a volunteer to be the scribe, or designate one if no one volunteers. 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, scribe notes for a Monday lecture are due at 2pm the following Monday, and similarly scribe notes for a Wednesday lecture are due at 2pm the following Wednesday (regardless of any intervening holidays). 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 follow, along with the number of hours of instruction devoted to each topic and the corresponding chapters of the Arora-Barak text.

Topic 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 under any circumstances, resulting in zero credit for the corresponding assignment.