We will go over the fundamental techniques for designing exact exponential algorithms for fundamental NP-hard problems. We will mainly follow the book
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..)
4) (Apr 1) Treewidth, Chapter 5 in FK. Yonatan Itai
5) (Apr 22) Measure and Conquer, Chapter 6 in FK. Shlomo Waknine
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
8) (May 20) Local search and SAT, Chapter 8 in FK. Shahar Lewkowicz
9) (May 27) An Improved Exponential-time Algorithm for k-SAT, Paturi, Pudlak, Saks, Zane, JACM 52(3), 2005. Tal Lancewicki
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