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 1012. (Note: On Friday February 3
Rocco's office hours will be 9:4511:45.)
Email: rocco at cs dot columbia dot edu.
TA: Adam Freilich (adam dot m dot freilich at gmail dot com, office hours Wed 1012, 464 CSB)
Room: 415 Schapiro
Time: Thurs 10:1012:40
COMS E6998 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 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.
Motivation
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 lowlevel
study of computation often play a role in "highlevel" complexity.
The focus of this course is on the second strand: concrete, "lowlevel"
complexity, with a special focus on lower bounds (though we will do some
upper bounds too). We will give selfcontained 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.
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. 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 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.
 Boolean formula complexity: Basic definitions, examples.
Nonconstructive lower bounds by counting arguments (Shannon).
Classical de Morgan formula size lower bounds (Subbotovskaya, Khrapchenko,
Andre'ev). Positive results: depth reduction (Spira), amplification (Valiant). Relation with communication complexity, depth lower bounds (Karchmer/Wigderson, Grigni/Sipser). Fullbasis formula lower bounds (Neciporuk).
 Decision trees and branching programs: Basic definitions,
examples. DT depth versus certificate complexity (Blum/Impagliazzo).
DT size versus CDNF size: upper and lower bounds
(Ehrenfeucht/Haussler, Jukna/Savicky/Razborov/Wegener).
Branching program basics. Lower bounds for boundedwidth branching
programs (Alon/Maass). Boundedwidth branching programs can compute
anything in NC1 (Barrington).
 Boundeddepth circuits: Basic definitions, examples.
Switching Lemma (Hastad, Razborov) and how it yields boundeddepth circuit lower bounds.
Voting polynomials and lower bounds for bounded depthcircuits with majority
gates (Aspnes/Beigel/Furst/Rudich, Beigel).
Lower bounds for boundeddepth circuits with mod gates (Razborov/Smolensky).
 Threshold circuits: Single threshold gates: basic properties.
Communication complexity based lower bounds for
Depth2 threshold circuits, decision trees of threshold circuits (Nisan).
 Monotone circuits: Basic definitions, examples.
Classical results: how many negations do circuits for nonmonotone
functions need? (Markov, Fischer). Superpolynomial lower bounds
for monotone circuits (Razborov, Andre'ev). Approximating monotone functions
(Bshouty/Tamon).
Class Requirements
The requirements of the course are as follows:

Attendance and class participation:
Students are expected to come to lecture and are encouraged to to participate.
 Sporadic homework (10% 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 at least half of the homework problems by the last lecture (10:10am on April 27). Here is a list of the official homework problems (this list will be updated as the semester progresses).
 Scribe notes (30% 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. I will provide a template and will 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 (60% of grade): Each student will select a topic
in concrete complexity, write a progress report midsemester, give a presentation and write a final report
on that topic.
Topic selection: The projects page lists potential broad 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.
Readings
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.
 Lecture 1 (1/19/2017): Course
overview and introduction, Boolean formula basics and examples,
Shannon's nonconstructive lower bound via counting, Subbotovskaya's lower bound via random restrictions.
 Lecture 2 (1/26/2017):
Andre'ev's lower bound on Boolean formula size. Spira's ``depth reduction''
for Boolean formulas. Valiant's probabilistic construction of small monotone
formulas for MAJ using amplification.
 Lecture 3 (2/2/2017):
Finished Valiant's construction.
Basics of communication complexity of functions and relations:
protocol trees, monochromatic rectangles. Khrapchenko's lower bound
on partitioning communication matrix into monochromatic rectangles.
 Lecture 4 (2/16/2017):
Equivalence between Boolean formulas
and communication protocols for corresponding relation.
Similar equivalence between monotone formulas and communication
protocols for monotone relation. Start of Omega(log^2(n)) lower bound for
monotone formula size of st connectivity via reduction to FORK.
 Lecture 5 (2/21/17):
Finish lower bound on deterministic communication complexity of FORK.
Fullbasis formulas: an (almost) n^2 lower bound via strippeddown
Neciporuk. Decision trees: basics, evasive functions, DNFs as "nondeterministic decision trees."
 Lecture 6 (2/23/17):
DTdepth is at most DNFwidth * CNFwidth. DTsize is at most n^{log^2(CDNFsize)}. Basics of Fourier analysis over {1,1}^n, towards proving DTsize can be as large as 2^{\Omega(log^2(CDNFsize))}.
 Lecture 7 (3/02/17):
Finished proof that DTsize can be >= 2^{log^2(CDNFsize)}. Basics of branching programs. Neciporuk's theorem, and using it to get an (almost) n^2 lower bound on general branching program size for Element Distinctness.
 Lecture 8 (3/23/17):
Background on branching program lower bounds. Construction of O(n*polylog(n))size branching program for EXACT via Chinese Remainder Theorem. Start proof of
\Omega(n*loglogn) lower bound on constantwidth branching programs for Majority (Alon/Maass).
 Lecture 9 (3/28/09):
Finish proof of Alon/Maass lower bound. Begin proof of Barrington's Theorem:
algebraic formulas, linear bijection straightline programs.
 Lecture 10 (3/30/09):
Finish proof of Barrington's Theorem. Start unit on constantdepth circuits:
easy lower bound for DNFs / CNFs computing Parity. 2^{O(n^{1/(d1)})} upper bound on depthd circuits for Parity. Switching Lemma, begin proof that depthd circuits for Parity require size 2^{\Omega(n^{1/(d1)})} (using the Switching Lemma).
 Lecture 11 (4/6/17):
Finish proof that depthd circuits for Parity require size 2^{\Omega(n^{1/(d1)})} (using the Switching Lemma). Proof of weak version of the Switching Lemma
with failure probability (40s2^s)^t (based on sclipped decision trees).
 Lecture 12 (4/13/17):
Computing PAR with two layers of MAJ gates. Polynomial threshold functions,
PTF degree, weak PTF degree. Start proof of [ABFR]:
depthd circuits with a MAJ on top that compute PAR require size 2^{\Omega(n^{1/(4d)})}.
 Lecture 13 (4/20/17):
Finish [ABFR] proof. Proof of theorem of Razborov: constantdepth circuits
with AND, OR, PARITY gates require 2^{n^{\Omega(1)}} size to compute the
MAJ function.
 Lecture 14 (4/27/17):
Linear threshold functions, lower bounds on restricted classes
of threshold circuits (Nisan, "Communication Complexity of
Threshold Gates").
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.