Professor  Alexander Sherstov  
my last name @cs.ucla.edu  
Quarter  Winter 2019  
Room & Time  TR 2–3:50pm (Boelter 4413)  
Office Hours  TR 4–4:30pm (Engineering VI, Room 464)  
Webpage  http://www.cs.ucla.edu/~sherstov/teaching/2019winter  
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 NPcompleteness, 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 writeup 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.


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.
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 AroraBarak text.
Topic  Lecture Hours  Chapter 
Deterministic computation  3  1 
Nondeterminism  4  2 
Diagonalization  5  3 
Space complexity  4  4 
Polynomial hierarchy  2  5 
Midterm  
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.