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

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 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

Homework

List of Topics

• General introduction: Overview of worst-case and average-case lower bounds, pseudorandom generators, and deterministic approximate counting, and some connections between them. Quick overview of (some of the) computational models we'll consider.

• Boolean formulas: Non-explicit lower bounds (worst-case and average-case). Lower bounds of Subbotovskaya and Andreev via random restrictions and shrinkage for explicit functions. Neciporuk-style worst-case lower bound for full-basis formulas.

• Low-depth Boolean circuits: ``Bottom-up'' lower bounds via random restrictions; the Switching Lemma of Hastad and Razborov. Average-case lower bounds. O'Donnell-Wimmer's average-case lower bounds for depth-2 circuits. Top-down (worst-case) lower bounds for very shallow circuits.

• F_2 polynomials: Average-case lower bounds (correlation bounds) for large degree but large correlation. Average-case lower bounds (correlation bounds) for small degree and small correlation.

• Basic tools for PRGs: bounded independence, small-bias distributions, bounded-independence small-bias distributions. Applications to fooling juntas, decision trees, Fourier L_1-bounded functions. Sandwiching polynomials.

• Fooling low-degree F_2 polynomials: Viola's theorem.

• Applications of bounded independence: Fooling constant-depth circuits (Braverman's theorem).

• Linear threshold functions: PRGs via bounded independence. Deterministic approximate counting. A peek at polynomial threshold functions.

• Pseudorandom generators from average-case hardness: the Nisan-Wigderson generator. Applications.

• PRGs from "recycling randomness": Impagliazzo-Nisan-Wigderson, Impagliazzo-Meka-Zuckerman generators. Applications.

• Fractional PRGs and polarizing random walks: Applications.

• Pseudorandom generators from random restrictions: the Ajtai-Wigderson framework. Applications.

• More pseudorandom generators from random restrictions: the Impglazzo/Meka/Zuckerman generator. Applications.

Class Requirements

• Attendance and class participation (10% of grade) Students are expected to come to lecture and are encouraged to to participate.

• Sporadic homework (15% of grade): Occasionally in lecture I will state a result in class without proof and designate its proof as an "official homework problem." You don't need to do every homework problem, but you must complete and turn in three homework problems over the course of the semester (one by Feb 15, one by March 15, one by April 15). Here is a list of the official homework problems (this list will be updated as the semester progresses).

• Scribe notes (25% of grade): Each student will prepare scribe notes for one or more lectures during the semester. This should be a clear and readable exposition of the material covered in that lecture. We will provide a template and give you feedback on your notes. You are encouraged to use outside sources (in particular, relevant surveys and papers) to make your notes as good as possible.

• Final project (50% of grade): Each student will select a topic in concrete complexity, write a progress report along the way, give a presentation, and write a final report on that topic. The last few lectures will be devoted to student presentations.

  Topic selection: The projects page lists many possible topics; you are also encouraged to come up with your own topic.

  Progress report: About a month before the final project due date you will turn in a progress report describing what you've done and outlining goals for your presentation; see the projects page for details.

  Presentation: The goal of your presentation should be to give a comprehensible explanation of an important result in your topic (this is the goal for the instructor in his lectures on the topics he covers as well). Presentations will take place towards the end of the semester. The length of each presentation will be determined based in part on the number of students in the class.

  Final report: The final report will have two components. (1) Background: explain the topic and give a clear and thorough exposition of prior work on this topic. This should include at the very least a detailed set of 'scribe notes' for the material covered in your presentation; since the presentations are not likely to be very long, this background section should likely cover additional material not in your presentation as well. (2) Research: Identify an interesting and worthwhile research question in this area and describe why the question is interesting and your work on this question. Students are encouraged to spend significant effort on the research component; ideally, this portion of the project will lead to a new publishable research result in the topic you pursue, but this is not necessary in order to do a successful project.

  
  You will turn in an initial proposal fairly early in the semester (basically just to identify the topic for your project). See the projects page for a detailed schedule.
  

Scribe Notes and Lecture Notes

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.

• Lecture 1: (1/16/2024) Course overview and introduction (administrative and technical). Restricted models of computation: some examples. Randomness in computing: the basics. Worst-case and average-case lower bounds. Pseudorandom generators for restricted models. PRGs imply worst-case lower bounds.

  Readings: Hatami/Hoza Chapter 1, Chapter 4.1. Scribe notes. Notes from lecture

• Lecture 2: (1/23/2024) PRGs imply average-case lower bounds. Boolean formulas: the basics. Shannon's non-constructive lower bound based on counting. Subbotovskaya's lower bound via random restrictions and "shrinkage." Andre'ev's function and lower bound.

  Readings: Boppana/Sipser (particularly Section 2.2, 5.3). Jukna Section 6.1, 6.3, 6.4. Scribe notes. Notes from lecture

• Lecture 3: (1/30/2024) Depth reduction for Boolean formulas. Full-basis Boolean formulas. Constant-depth circuits: basics, intuition, upper bound. The Switching Lemma.

  Readings: Jukna Section 6.1, Section 12.1, 12.2. Boppana/Sipser Section 3.3, 3.4). Scribe notes. Notes from lecture

• Lecture 4: (2/06/2024) How the Switching Lemma gives exponential lower bounds for parity. Warmup: a "baby" switching lemma and its proof. Proof of Hastad's Switching Lemma.

  Readings: as above, plus Section 1 of Thapen's notes on switching lemmas, Section 2 of Beame's switching lemma primer. Scribe notes. Notes from lecture

• Lecture 5: (2/13/2024) Finish proof of the Switching Lemma (the "Key Fact"). Average-case lower bounds from the Switching Lemma. O'Donnell/Wimmer correlation bound for super-large depth-2 circuits. Basics of F2-polynomials.

  Readings: as above, plus O'Donnell/Wimmer Approximation by DNFs: examples and counterexamples. Scribe notes. Notes from lecture

• Lecture 6: (2/20/2024) Weak correlation bound for fairly-high-degree F2 polynomials (Smolensky). Strong correlation bound for fairly-low-degree F2 polynomials (Babai/Nisan/Szegedy, Viola/Wigderson). Start basic tools for PRGs.

  Readings: as above, plus Section 1.2 of Viola's "On the Power of Small-Depth Computation"; see also Section 1 of Viola's "Correlation bounds against polynomials" and Viola/Wigderson Norms, XOR lemmas, and lower bounds for polynomials and protocols. See also the original Smolensky paper and the original Babai/Nisan/Szegedy paper. Scribe notes. Notes from lecture

• Lecture 7: (2/27/2024) Finish necessary facts about k-uniformity. Basic tools for PRGs: k-wise independent, eps-biased, k-wise independent eps-biased.

  Readings: Hatami/Hoza Sections 2.1-2.3. Scribe notes. Notes from lecture

• Lecture 8: (3/05/2024) Fourier interlude/applications of basic tools for PRGs from last lecture. Sandwiching approximators and fooling. Viola's theorem: sum of eps-biased generators fools degree-d F2 polynomials.

  Readings: Hatami/Hoza Sections 2.3, 2.4. Viola's paper. Scribe notes. Notes from lecture.

• Lecture 9: (3/19/2024) Finish proof of Viola's theorem: sum of eps-biased generators fools degree-d F2 polynomials. Start proof of Braverman's theorem: any k-wise independent random variable fools AC0. Background results on BRS and LMN low-degree polynomial approximators for AC0.

  Readings: Braverman's paper. The papers of Linial, Mansour and Nisan and Beigel, Reingold and Spielman that it builds on. Scribe notes. Notes from lecture.

• Lecture 10: (3/26/2024) Finish proof of LMN approximator. Proof of Braverman's theorem: any k-wise independent random variable fools AC0. Linear threshold function basics: examples, regularity, Berry-Esseen. Start PRGs for linear threshold functions (bounded independence).

  Readings: As above. The paper of DGJSV on bounded independence fooling LTFs. Scribe notes. Notes from lecture.

• Lecture 11: (4/02/2024) Linear threshold functions: regularity, Berry-Esseen. PRGs for linear threshold functions (bounded independence fools LTFs): the regular case. Structure theorem for LTFs.

  Readings: As above. We didn't cover it, but if you're interested, check out the paper of Gopalan, Klivans and Meka on deterministic approximate counting for LTFs. Scribe notes. Notes from lecture.

• Lecture 12: (4/09/2024) Survey of some known PTF results: state of the art for PRGs, deterministic approximate counting. Sketch of deterministic approximate counting for degree-2 PTFs. The Nisan-Wigderson generator and using it to fool AC0.

  Readings: Papers of Meka and Zuckerman and Kane on fooling PTFs. Papers of DS and DDS on deterministic approximate counting for PTFs. The original paper of Nisan and Wigderson giving the Nisan-Wigderson generator (see also Section 4.2 of Hatami/Hoza as well as many other sources for this). Scribe notes. Notes from lecture.

Academic Honesty Policy