| Professor | Alexander Sherstov | |
| my last name @cs.ucla.edu | ||
| Quarter | Spring 2012 | |
| Room | MS 5203 | |
| Time | Monday and Wednesday 4-5:50pm | |
| Office Hours | Wednesday 2:30-3:30pm, BH 3731J | |
| Webpage | http://www.cs.ucla.edu/~sherstov/teaching/2012-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 4pm the following Monday, and similarly scribe notes for a Wednesday lecture are due at 4pm the following Wednesday. Email me your .pdf file and the source files (.tex and .bib, as well as figure files if any), preferably all in a single ZIP archive.
|
Instructions | |
Template |
Midterm and final. There will be two in-class exams, a midterm and a cumulative final exam. You will not be allowed to use the textbook or your own notes on the exams. 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, including academic honesty and regrade requests.
Participation. Attendance and class participation are essential for success in this course. Please do you best to attend every lecture and always be on time. Keep in mind that if you are absent without a documented excuse, I will not be able to go over missed lecture material during office hours or over email. 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. Class participation will be graded on a credit/no credit basis individually for every lecture. The participation grade for the course will then be computed by averaging these binary scores over all lectures.
|
|
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 available in graduate courses at UCLA.
This course will cover in detail Chapters 1–8, 11, 14, 17, 20–22 of the Arora-Barak textbook. A tentative schedule of topics is as follows, with bullets indicating how many lectures will be devoted to a given topic.
| Topic | Lectures | Chapter |
| Computability and the class P | • | 1 |
| Nondeterminism and NP-completeness | • | 2 |
| Diagonalization | • | 3 |
| Oracle machines | • | 3 |
| Space complexity | • | 4 |
| Polynomial hierarchy | • | 5 |
| Randomized computation | • | 7 |
| Boolean circuits | • | 6 |
| Midterm | • | |
| Circuit lower bounds | • • | 14 |
| Interactive proofs | • | 8 |
| Complexity of counting | • | 17 |
| Derandomization | • | 20 |
| Pseudorandom constructions | • • | 21 |
| PCP theorem | • • • | 11, 22 |
Attendance and class participation. Attendance is essential for success in this course. If you are absent without a documented excuse, I will not be able to go over missed lecture material during office hours or over email. 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 submissions of scribe notes will not be accepted, resulting in zero credit for the activity. No distinction will be made between submissions late by a split second and submissions never received. If this seems harsh to you, ask yourself the following question: if I really cared about this class and my progress in it, would I wait until a split second before the deadline to submit my work? Similarly, the students are expected to report to class on time. Late arrivals are disruptive to a class in session and will count as an absence, with zero credit for class participation on that day.
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.
Regrade requests. Requests for a regrade must be made no later than one week after the graded assignments have been handed out in class, regardless of whether you attended class that day. Please put your request in writing, indicating the parts you want regraded and why, and hand your request to me in person. As usual, please keep in mind the unlikely but real possibility that a regrade may lower your grade, in case a previously overlooked mistake is discovered.
Cell phone use. Use of cell phones, laptops, or other electronic devices during class is distracting to the instructor and other students and is forbidden. Please ensure that your phone and any other devices are in silent mode for the duration of class.