COMS 6998: Advanced Topics in Computational Complexity
Spring 2017

General Information | Motivation | Prerequisites | Topics | Class Requirements | Readings | Scribe Notes

General Information

Instructor: Rocco Servedio (517 CSB, office hours Fri 10-12. (Note: On Friday February 3 Rocco's office hours will be 9:45-11:45.) Email: rocco at cs dot columbia dot edu.
TA: Adam Freilich (adam dot m dot freilich at gmail dot com, office hours Wed 10-12, 464 CSB)
Room: 415 Schapiro
Time: Thurs 10:10-12:40

COMS E6998 is a three-credit advanced graduate level course on computational complexity. The course can be used as a theory elective for the Ph.D. program in computer science, as a track elective course for MS students in the "Foundations of Computer Science" track, or as a track elective for undergraduates in the "Foundations" track. Auditing the class requires the approval of the instructor.

If you are a student in Columbia College, General Studies or Barnard who would like to register for this class, please contact me with a brief description of your background in CS theory and mathematics courses.


Complexity theory is the study of the inherent hardness (or easiness) of computational tasks. It is a vast field.

Very roughly speaking, one can divide research in computational complexity into two main strands. One of these strands deals with "high level" complexity questions: is space a more powerful resource than time (i.e. is P properly contained in PSPACE)? Does randomness enhance the power of efficient computation (i.e. is P properly contained in BPP)? Is it easier to verify a proof than to construct one (i.e. is P properly contained in NP)? Of course, we do not know the answers to any of these questions; thus most results in "high level" complexity are conditional results that rely on various unproven assumptions such as P != NP. While many interesting connections have been established between different computational problems and computational resources, and many beautiful and important results have been achieved, the major open questions here are unanswered and seem likely to stay that way for the foreseeable future.

A second strand of research in complexity theory deals with establishing concrete lower bounds. This is essentially a "low level" study of computation; it typically centers around simple models of computation such as decision trees, Boolean formulas, restricted classes of Boolean circuits, and the like. In this line of research unconditional lower bounds are established which rely on no unproven assumptions, but such results are only known for various restricted models of computation such as the examples given above. There has been steady progress made over the years using a range of techniques from combinatorics, algebra, analysis, and other branches of mathematics. Results and techniques from this low-level study of computation often play a role in "high-level" complexity.

The focus of this course is on the second strand: concrete, "low-level" complexity, with a special focus on lower bounds (though we will do some upper bounds too). We will give self-contained proofs of a wide range of unconditional lower bounds for interesting and important models of computation, covering many of the "gems" of the field that have been discovered over the past several decades. There will be an emphasis on techniques and we will highlight many open questions along the way. Students will prepare scribe notes, do a few homework exercises, study research papers, and work on a research project as the main activities in the class. Thus the course should serve as a good introduction to research in concrete computational complexity.


The most important prerequisite is "mathematical maturity"; you should be comfortable with proofs, basic discrete math, combinatorics, probability, and linear algebra. We will use discrete Fourier analysis over the Boolean hypercube at various places in the course but this machinery will be developed from scratch. A solid undergraduate-level mathematics background is good preparation. If you have questions about your mathematical readiness you should contact the instructor before enrolling.

The course will not include any programming.

COMS 4236 (Introduction to Computational Complexity) is good preparation, but this is mostly for the perspective that it provides; we will rarely if ever be relying on results from COMS 4236. The course can be taken concurrently with COMS 4236.

List of Topics

This is a rough list of anticipated topics which is subject to change. We may skip some of these or cover additional topics as determined by time and the interest/background of the couse participants.

Class Requirements

The requirements of the course are as follows:


There is no single textbook for the material we will cover, though a nontrivial amount of the material (along with a lot of other nice stuff) is the book "Extremal combinatorics with applications in computer science" by Jukna. Another excellent reference that is very relevant to this course is a different book, "Boolean Function Complexity," by Jukna. An older but still very nice resource is the survey article by Boppana and Sipser, which you can find here.

Scribe Notes

Information for scribes: Work with your fellow scribe to prepare one set of scribe notes. Please turn these via email, to coms6998complexitys17 at gmail dot com, by one week after your lecture. Course staff will give you feedback on the notes relatively quickly, which may include a request for some revisions; you should then turn in the final revised notes no later than two weeks after your lecture (but earlier is great) and they will be posted online.

Click here for a template and style files. Click here for sample scribe notes (from a different course) which are at a good level of detail -- in particular, it's helpful to use full sentences, write down precise definitions and theorem statements (even if we were more informal in class), include examples, use figures, etc.

Academic Honesty Policy

By taking the course, students are presumed to consent to the Computer Science departmental policy on academic honesty. This policy has been passed by the faculty of the Department and approved by the school deans. The policy will be enforced for all courses, including this one. You can find the text of the policy at For this course in particular, students should be sure to provide appropriate citations for all sources used in their project reports.