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