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 (video part1 part2, slides: pdf, ppt)
11) (June
10) Deteminant
Sums for Undirected Hamiltonicity, Bjorklund, SICOMP 43(1), 2014. Aviv Engelberg (video part1 part2, slides: pdf, ppt)
12) (June 17) Exact
Exponential Algorithms for Two Poset Problems, Laszlo
Kozma. Ariel Litmanovich (video part1 part2, slides: pdf,
ppt)
13) (June 24) Lower bounds based
on the Exponential Time Hypothesis, Lokshtanov, Marx,
Saurabh, some material is also 11.3 in FK. Itay Sason
(video part1 part2, slides: pdf, ppt)