This course will cover two subjects in complexity that have particularly come to the fore in recent years:

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.

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.

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

- 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