Seminar on exact exponential algorithms, Spring 19/20

Haim Kaplan

We will go over the fundamental techniques for designing exact exponential algorithms for fundamental NP-hard problems. We will mainly follow the book

§  Exact exponential algorithms, Fomin, Kratsch, 2010 (FK)

and some additional more recent papers. Lectures may depend on previous ones so it is strongly recommended that you follow the material closely and read ahead using this book.

I would like to meet each one of you at least a week before your lecture (I recommend you do it as early as possible in case we need more than one meeting or there are some difficult proofs to understand). We will go over your planned lecture and your slides/notes.

I suggest you start reading your material as soon as possible, I am available for any question you may have, either regarding the technical material or regarding planning the parts you will deliver and how.

If you would like to do the first student’s lecture on Mar 18 please contact me (even before semester starts..)

Schedule

1)    (Mar 11) An introductory lecture, Exact Exponential Algorithms, Fomin, Kaski, CACM 56(3) 2013.

2)    (Mar 18) Dynamic programming, Chapter 3 in FK. Guy Korol (video, slides: pdf, ppt)

3)    (Mar 25) Inclusion Exclusion, Chapter 4 in FK. Keren Solodkin (video part1 part2, slides: pdf, ppt)

4)    (Apr 1) Treewidth, Chapter 5 in FK. Yonatan Itai (video part1 part2, slides: pdf, ppt)

5)    (Apr 22) Measure and Conquer, Chapter 6 in FK. Shlomo Waknine (video part1 parts, slides: pdf, ppt)

6)    (May 6) Subset convolution, Chapter 7 in FK, you can also base this on the paper Set Partitioning via Inclusion Exclusion, Bjorklund, Husfeldt, Koivisto, SICOMP, 39(2), 2009. Ido Bayda (video part1 part2, slides: pdf, ppt)

7)    (May 13) Trimmed Moebius Inversion and Graphs of Bounded Degree, Bjorklund, Husfeldt, Kaski, Koivisto Theory of Computer Systems 47, 2010. Bar Ashner (video part1 part2, slides: pdf, ppt)

8)    (May 20) Local search and SAT, Chapter 8 in FK. Shahar Lewkowicz (video part1 part2, slides: pdf, ppt)

9)    (May 27) An Improved Exponential-time Algorithm for k-SAT, Paturi, Pudlak, Saks, Zane, JACM 52(3), 2005. Tal Lancewicki (video part1 part2, slides: pdf, ppt)

10)  (June 3) Time versus space, Chapter 10 in FK. Or Castel

11)  (June 10) Deteminant Sums for Undirected Hamiltonicity, Bjorklund, SICOMP 43(1), 2014. Aviv Engelberg

12)  (June 17) Exact Exponential Algorithms for Two Poset Problems, Laszlo Kozma. Ariel Litmanovich

13)  (June 24)  Lower bounds based on the Exponential Time Hypothesis, Lokshtanov, Marx, Saurabh, some material is also 11.3 in FK.  Itay Sason