Professor  Alexander Sherstov  
my last name @cs.ucla.edu  
Quarter  Winter 2016  
Room and Time  MW 2–3:50pm, Boelter 5264  
Office Hours  MW 1:30–2pm, Boelter 3731J  
Webpage  http://www.cs.ucla.edu/~sherstov/teaching/2016winter  
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 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 the other 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 follow, along with the number of hours of instruction devoted to each topic and the corresponding chapters of the AroraBarak text.
Topic  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 the other students.
Late policy. Late work will not be accepted under any circumstances, resulting in zero credit for the corresponding assignment.