Seminar on Fine-Grained Algorithms and Complexity (Fall 2018)

This seminar is about exact exponential-time algorithms and ETH based hardness results, with emphasis on counting problems.

Date Topic References
9/14/2018 Introduction to fine-grained complexity and algorithms; ETH and SETH; Orthogonal Vectors The slides of the first lecture of Ryan Williams's course
9/21/2018 Fine-grained counting complexity; #ETH; Ryser's formula; Fast convolution Holger Dell's talk; Chapter 10 of Parameterized Algorithms
9/28/2018 Sparsification Lemma of k-CNF (Speaker: Yijia Chen) Impagliazzo, Paturi and Zane's paper
10/12/2018 Sparsification Lemma of k-CNF cont'd (Speaker: Yijia Chen)
10/19/2018 Radu Curticapean's block interpolation method; Tight #ETH lower bound for Permanent Radu Curticapean's paper
11/02/2018 Color-coding; FPT-RAS for k-path; Perfect hash family Chapter 5 of Parameterized Algorithms; Chaper 13 of Parameterized Complexity Theory; Arvind and Raman's paper
11/09/2018 Extensor-coding; Faster algorithm for sampling k-path Brand, Dell and Husfeldt's paper
11/30/2018 Valiant-Vazirani's isolation lemma; Approximate counting with an NP-oracle Valiant and Vazirani's original proof
12/7/2018 An isolation lemma for k-SAT (Speaker: Dominik Scheder) The paper of Calabro, Impagliazzo, Kabanets and Paturi.
12/14/2018 Graph algorithms via random walk (Speaker: Yu Gao) The paper of Durfee, Gao, Goranci and Peng.
1/4/2019 Fine-grained reductions from approximate counting to decision The paper of Holger Dell and John Lapinskas.