COMS 6998: Unconditional Lower Bounds and Derandomization
Spring 2024

General Information | Motivation | Prerequisites | Readings | Homework | Topics | Class Requirements | Projects | Scribe Notes, Lecture Notes, and Readings | Academic Honesty Policy

General Information

Instructor: Rocco Servedio (517 CSB, office hours by appointment.) Email: rocco at cs dot columbia dot edu.
TA: Yuhao Li (yuhaoli at cs dot columbia dot edu)
Room: Mudd 1024
Time: Tues 1:10-3:40 pm

This 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 an undergraduate student in SEAS, 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.

Motivation

Complexity theory is the study of the inherent hardness (or easiness) of computational tasks. It is a very big and very glorious field.

Roughly speaking, one can divide research in computational complexity into two main strands. One of these strands dwells with angels in the Great Beyond and deals with "high level" complexity questions: 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 either of these questions; most results in "high level" complexity are conditional results that rely on various unproven assumptions such as P != NP or P=BPP. 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 is rooted down in the mud with the worms and grubs; it deals with establishing unconditional results. This is essentially a "low level" study of computation; it typically centers around simple models of computation such as decision trees and branching programs, Boolean formulas and restricted classes of Boolean circuits, different types of polynomials, and so on. In this line of research unconditional results are established which rely on no unproven assumptions, but we are only able to achieve such results for various restricted models of computation such as the examples given above. There has been steady progress made here over the years using a range of techniques from combinatorics, algebra, analysis, probability, 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. Our focus will be on unconditional results in the direction of P != NP (i.e., lower bounds for restricted models of computation) and in the direction of P=BPP (i.e., derandomization results and, in particular, pseudorandom generators for restricted models of computation). We will study a wide range of unconditional lower bounds and derandomization results for interesting and important models of computation, covering many "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 and unconditional derandomization.

Prerequisites

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.) In particular, you should be completely comfortable with the probability basics covered in this brief note, and you should be comfortable with using the tail bounds covered in this brief overview of standard tail bounds. In general, 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 largely for the perspective that it provides; we will occasionally make reference to concepts from COMS 4236 but we will rarely require results / proofs from that class.

Readings

There is no single source for the material we will cover, but the book by Jukna on Boolean function complexity is a comprehensive resource for many lower bounds, and the recent excellent survey of Hatami and Hoza is a great source for many of the PRG results we'll cover. Links to specific readings for each lecture will be posted as the semester progresses.

Homework

Here is a list of the official homework problems (this list will be updated as the semester progresses). Recall that you need to turn in one HW problem by Feb 15, one HW problem by March 20, and one HW problem by April 15. All HW problems should be turned in using Gradescope.

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:

Scribe Notes and Lecture Notes

Information for scribes: Work with your fellow scribe (if there is one) to prepare one set of scribe notes. Please turn these via email (to both Rocco and Yuhao) by five days after your lecture (i.e. by EOD on the Sunday 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 (by email to both Rocco and Yuhao) no later than twelve days after your lecture (EOD the following Sunday) 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, you should 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 http://www.cs.columbia.edu/education/honesty. For this course in particular, students should be sure to provide appropriate citations for all sources used in their project reports.