These papers contain some of the ideas for the content of the course. Sometimes these will be conference and sometimes the journal version depending the clarity of the presentations.
Algorithms for SAT:
R. Paturi, P. Pudlak, F. Zane, Satisfiability Coding Lemma} FOCS 1997, journal 1999. Introduced the PPZ algorithm for SAT.
U. Schoening, A probabilistic algorithm for k-SAT based on limited local search and restart FOCS 1999, journal 2002. Introduced and analyzed a random walk SAT algorithm.
R. Paturi, P. Pudlak, M. Saks, F. Zane, An improved exponential-time algorithm for k-SAT FOCS 1998, journal 2005. Improved algorithm for SAT based on adding local inferences to PPZ.
The Exponential Time Hypothesis:
R. Impagliazzo, R. Paturi, F. Zane, Which problems have strongly exponential complexity? FOCS 1998, journal 1999. Defined sub-exponential reductions and proved sparsification lemma for k-SAT.
R. Impagliazzo, R. Paturi, On the complexity of k-SAT FOCS 1999, journal 2001. Introduced ETH and argued for its robustness. Also introduced SETH in an open problem at the end.
C. Calabro, R. Impagliazzo, R, Paturi, A Duality between Clause Width and Clause Density for SAT CCC 2006, no journal version. Gave improved sparsifcation algorithm and analysis as well as further evidence for SETH.
C. Calabro, PhD Dissertation: The Exponential Complexity of Satisfiability Problems 2009. Gives full details of improved sparsification algorithms
Reductions from SETH, ETH: Fine-grained Complexity Results
R.R. Williams, A New Algorithm for Optimal Constraint Satisfaction and its Implications (Arxiv version, also at ICALP 2004, 2005 journal) A small note in Section 5.1 hints at the reduction for Orthogonal Vectors. In the later versions this is replaced by the Subset Query problem.
K. Bringman, M. Kunn\"emann, Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping (FOCS 2015, Arxiv Version). Gives binary version for LCS hardness.
A. Abboud, PhD Dissertation: Hardness within P 2017.
Lifting Theorems
R. Raz, P. McKenzie, Separation of the Monotone NC Hierarchy FOCS 1999, First version of thickness-based lifting with Index that produces monotone depth lower bounds from Resolution depth
M. Göös, T. Pitassi, Communication Lower Bounds via Critical Block Sensitivity FOCS 2012 (2016 Arxiv revision) Generalizes depth lifting for clause search and to other specialized gadgets
M. Göös, T. Pitassi, T. Watson Deterministic Communication vs. Partition Number (FOCS 2015, Arxiv version) Simplifies and improves Raz-McKenzie thickness-based lifting and applies it to find a quadratic separation between log of the partition number and deterministic communication complexity
A. Chattopadhyay, M. Koucký, B. Loff, S. Mukhopadhyay, Composition and Simulation Theorems via Pseudo-random Properties (ECCC 2017) Extends thickness-based lifting to Inner Product
X. Yu, P. Yao, H. Yuen Raz-McKenzie simulation with the inner product gadget (ECCC 2017) Extends thickness-based lifting to Inner Product
M. Göös, T. Pitassi, T. Watson Query-to-Communication Lifting for BPP (FOCS 2017, 2020 journal version) Introduces density-restoring partition for min-entropy based lifting for Index in order to lift randomized query bounds to randomized communication complexity
X. Wu The uniform marginals lemma in [GPW17] (Manuscript 2018) Alternative proof of part of the uniform marginals lemma for Index
A. Garg. Göös, P. Kamath, D. Sokolov Monotone Circuit Lower bounds from Resolution (STOC 2018, journal version) Extends density-restoring partition and min-entropy based lifting for Index to lift Resolution width to yield exponential monotone circuit size lower bounds using DAG-like protocols. Yields exponential size lower bounds size even for monotone circuits over the reals and applies this to derive exponential lower bounds on the size of Cutting Planes refutations of unsatisfiable CNFs
A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, T. Pitassi Query-to-Communication Lifting using Low Discrepancy Gadgets (CCC 2019, 2021 journal version) Extends density-restoring partition ideas for min-entropy based lifting to Inner Product, or any low discrepancy gadget, yielding lifting from randomized decision tree lower bounds to randomized communication complexity. Introduces a much more tricky ``balanced" density-restoring partions.
S. Lovett, R. Meka, I. Mertz, T. Pitassi, X. Zhang Lifting with Sunflowers (ITCS 2022) Min-entropy based lifting for Index with best current bounds. Uses recent theorems on robust sunflowers. ArXiv version (Arxiv 2020) Contains details of simplified DAG lifting
Anup Rao Coding for Sunflowers (Discrete Analysis journal version, arxiv posting) Contains key lemma used to proof Full Range Lemma for lifting
Anup Rao Sunflowers: from Soil to Oil (Bulletin of the AMS, Jan 2023) Overview of Sunflower Lemma and Expectation Treshold Conjecture proofs and applications