This course will cover
two subjects in complexity that have particularly come to the fore in recent years:
Exponential time hypotheses and fine-grain complexity: Beyond P vs NP
Despite the best efforts of researchers for over 50 years since the P vs NP
question was formulated, the best algorithms we have for SAT and other
NP-complete problems are still exponential in the worst case and barely improve on brute force.
If these are representative of the correct level of complexity,
which seems a reasonable stronger conjecture than P ≠ NP,
our usual ways of proving relationships between NP problems need to be
rethought, both from a theoretical and practical point of view, and radically
new relationships between problems emerge, a subject termed "fine-grain complexity".
This yields surprising connections that have produced a web of problem-solving
relationships well beyond the usual resource-focused complexity classes,
for example, showing how improving existing polynomial-time algorithms for
well-known problems is tied to improving exponential-time algorithms for SAT.
LIfting
A number of longstanding problems in computational complexity have been resolved in the last decade by showing how simple forms of function composition let us convert
hardness results proven in weak models of computation into hardness results for more powerful models of computation, a methodology that has been termed "lifting". We discuss lifting techniques and the some of the longstanding problems resolved using them. We then focus on a number of open problems and approaches to resolving them.
Logistics
- Instructor: Paul Beame
- Time and Place: Mondays and Wednesdays, beginning April 1, 2024 from 1:30-2:50 pm in CSE2 287.
Possibility of a couple of makeup lectures on Fridays at 1:30 based on student availability and interest.
- Work: Class participation and 2-3 light homework assignments to
ensure that everyone gets a bit of hands-on practice with the
material. Students are welcome and encouraged to work with
each other on the homework assignments.
Lecture Plan
- April 1: Introduction and Satisfiability algorithms (PPZ, PPSZ)
- April 3: Satisfiability algorithm (Schoening), ETH
- April 8: ETH, Sparsification (Zoom recording) (Notes)
- April 10 SETH, Orthogonal Vectors, Diameter approximation, k-SUM
- April 15 Problems related to Orthogonal Vectors, Polymomial Method algorithm for OV.
- April 17 Parameterized Complexity and implications for ETH, LCS
- April 22 Details of LCS lower bounds from SETH, Beyond SETH
- April 24 Beyond SETH continued: Circuit-SETH implies LCS lower bounds, Non-trivial Circuit-SAT speep-up implies circuit lower bounds.
- April 29 Methods for proving consequences of Circuit-SAT speed-up. DPLL SAT solvers and Tree-Resolution refutation.
- May 1` CDCL SAT solvers and Resolution refutations
- May 6` Exponential lower bounds for Resolution
- May 8` Communication Complexity and Karchmer-Wigderson games.
- May 13` Deterministic Lifting I
- May 15` Deterministic Lifting II
- May 20` Lifting using Min-Entropy I
- May 22` Lifting using Min-Entropy II: Sunflowers and the Full Range Lemma, DAG protocols
Resources
We will produce course notes on the class content. These will likely cover
somewhat more material than we will be able to go over in class.
Bibliography
This is a collection of some of the key papers and other materials related to
the development of these topics. We will add these in the course directory
and as we reach the corresponding portion of the course.