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:103:40 pm
This is a threecredit 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 lowlevel
study of computation often play a role in "highlevel" complexity.
The focus of this course is on the second strand: concrete, "lowlevel"
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
undergraduatelevel 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.
 General introduction: Overview of worstcase and averagecase 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: Nonexplicit lower bounds (worstcase and averagecase). Lower bounds of Subbotovskaya and Andreev via random restrictions and shrinkage for explicit functions. Neciporukstyle worstcase lower bound for fullbasis formulas.
 Lowdepth Boolean circuits: ``Bottomup'' lower bounds via random restrictions; the Switching Lemma of Hastad and Razborov. Averagecase lower bounds. O'DonnellWimmer's averagecase lower bounds for depth2 circuits. Topdown (worstcase) lower bounds for very shallow circuits.
 F_2 polynomials: Averagecase lower bounds (correlation bounds) for large degree but large correlation. Averagecase lower bounds (correlation bounds) for small degree and small correlation.
 Basic tools for PRGs: bounded independence, smallbias distributions, boundedindependence smallbias distributions. Applications to fooling juntas, decision trees, Fourier L_1bounded functions. Sandwiching polynomials.
 Fooling lowdegree F_2 polynomials: Viola's theorem.
 Applications of bounded independence: Fooling constantdepth circuits (Braverman's theorem).
 Linear threshold functions: PRGs via bounded independence. Deterministic approximate counting. A peek at polynomial threshold functions.
 Pseudorandom generators from averagecase hardness: the NisanWigderson generator. Applications.
 PRGs from "recycling randomness": ImpagliazzoNisanWigderson, ImpagliazzoMekaZuckerman generators. Applications.
 Fractional PRGs and polarizing random walks: Applications.
 Pseudorandom generators from random restrictions: the AjtaiWigderson framework. Applications.
 More pseudorandom generators from random restrictions: the Impglazzo/Meka/Zuckerman generator. Applications.
Class Requirements
The requirements of the course are as follows:

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
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.
 Lecture 1: (1/16/2024) Course overview and introduction (administrative and technical). Restricted models of computation: some examples. Randomness in computing: the basics. Worstcase and averagecase lower bounds. Pseudorandom generators for restricted models. PRGs imply worstcase lower bounds.
Readings: Hatami/Hoza Chapter 1, Chapter 4.1.
Scribe notes. Notes from lecture
 Lecture 2: (1/23/2024)
PRGs imply averagecase lower bounds.
Boolean formulas: the basics. Shannon's nonconstructive 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.
Fullbasis Boolean formulas.
Constantdepth 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"). Averagecase lower bounds from the Switching Lemma. O'Donnell/Wimmer correlation bound for superlarge depth2 circuits. Basics of F2polynomials.
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 fairlyhighdegree F2 polynomials (Smolensky).
Strong correlation bound for fairlylowdegree 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 SmallDepth 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 kuniformity. Basic tools for PRGs: kwise independent, epsbiased, kwise independent epsbiased.
Readings: Hatami/Hoza Sections 2.12.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 epsbiased generators fools degreed 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 epsbiased generators fools degreed F2 polynomials. Start proof of Braverman's theorem: any kwise independent random variable fools AC0. Background results on BRS and LMN lowdegree 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 kwise independent random variable fools AC0. Linear threshold function basics: examples, regularity, BerryEsseen. 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, BerryEsseen. 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 degree2 PTFs. The NisanWigderson 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 NisanWigderson 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
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.