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.