Deciding whether a graph on \(n\) vertices has a clique of size \(k\) is NP-hard. When \(k = 1000\), on the other hand, there clearly is a polynomial-time algorithm: Just test all 1000-tuples of vertices. But this takes time \(\Theta(n^{1000})\), and is clearly completely useless in practice!
Can the problem be solved in practice for small values of \(k\)? After all, it's not NP-hard for fixed \(k\). Can we find an algorithm whose running time depends not on \(n^{k}\), but is of the form \(f(k) n^{c}\), for a fixed constant \(c\) (that does not depend on \(n\)).
This question belongs to the area of parameterized algorithms. We consider NP-hard problems and look for algorithms that can solve them efficiently as long as some parameter of the problem instance is small.
We will study some techniques to develop parameterized algorithms:
We will meet many problems that have efficient parameterized algorithms, but for the clique problem above, no such algorithm has been found—and in fact we have evidence that none exists.
What kind of evidence would this be? Ideally, we would like to prove a lower bound on the complexity of a problem. But this is generally very hard, and most students never meet any lower bound in their studies except for the \(\Omega(n \log n)\) lower bound for comparison-based sorting.
We will generalize the sorting lower bound and prove \(\Omega(n \log n)\) lower bounds for a few interesting problems. Then we look at some recent approaches for arguing about lower bounds when one cannot prove such a bound. In particular, we will study lower bounds based on several assumptions:
Prerequisites: An algorithm course (CS300 or CS500 or equivalent), and some basic familiarity with NP-hardness. This course does not require any programming skills.
The class meets Wednesday from 16:00 to 17:15 and Fridays from 10:30 to 11:45 in room 3445 in the EECS building (E3-1). Lectures are given in English.
The grade will be composed as follows (small changes reserved): Participation (20%), Homework (40%), Exam (40%).
We will have a final exam on Wednesday, June 14, from 16:00 to 19:00, in classroom #1 (room 1101) in building E3-1 (not our usual classroom).
This term we will be using Piazza for class announcements, discussion, and asking questions.
Here is our Piazza class page.
You are responsible for checking the announcements on our Piazza class page regularly (if you make a Piazza account and enroll for the course, announcements will be mailed to you automatically.)
If you do not understand something, it is important that you ask questions. Piazza allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!
To ask questions, you need to register on Piazza and enroll as a student for CS700/MAS583. To do so, go to the enrollment page. Select "Join as student". You will then need to use your KAIST email address (ending with @kaist.ac.kr) to create an account.
Most of the material taught in this course stems from the last decade, so we will have to use some original papers as reference.
We will make use of the book Parameterized Algorithms, by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. It is available on-line through the KAIST library.
We will also use lecture notes by Jeff Erickson. The originals are on his webpage (or on older versions of this page).
We will use slides made by Karl Bringmann and Sebastian Krinninger for their class.
The last topic of the course uses material from Introduction to the Theory of Computation, Michael Sipser, Second International Edition, Course Technology 2006. Check out its errata page, which contains a few substantive (as opposed to stylistic) errors.
The course will be taught on the blackboard, so do not expect slides or other such lecture materials. If you miss a class, you'll have to ask a friend for their notes.
The material covered in the lectures so far:
| 03-03 | Introduction | Chapter 1 |
| 03-08 | Formal definitions of FPT and XP, Introduction to Kernelization | Sections 1.1, 2.1, 2.2.1 |
| 03-10 | Simple kernels | Sections 2.2.2, 2.2.3 |
| 03-15 | Crown decomposition | Section 2.3 |
| 03-17 | Kernels based on linear programming | Section 2.5 |
| 03-22 | Vertex cover search tree | Section 3.1 |
| 03-24 | Solving recursions, Feedback Vertex Set | Section 3.2, 3.3 |
| 03-29 | Vertex Cover above LP | Section 3.4 |
| 03-31 | VC above Matching, Variable-Deletion-Almost-2-SAT, Closest String | Section 3.5 |
| 04-05 | Lower bounds, decision trees, linear decision trees | decision tree notes, Section 7.1 and 7.2 in notes |
| 04-07 | Algebraic decision trees | Section 7.3 in the notes |
| 04-12 | Diameter, Maxgap, 3SUM-Hardness | 3SUM notes |
| 04-14 | 3SUM | |
| Midterm week (no class, no exam) | ||
| 04-26 | Parameterized reductions | Section 13.1 |
| 04-28 | Problems at least as hard as Clique | Section 13.2 |
| 05-03 | Holiday | |
| 05-05 | Holiday | |
| 05-10 | The W-hierarchy | Sections 13.3, 13.5 |
| 05-12 | ETH and SETH, SETH implies ETH | Sections 14.1, 14.2 |
| 05-17 | ETH bounds for FPT problems | Section 14.3 |
| 05-19 | ETH bound for CLIQUE, Orthogonal vectors hypothesis | Section 14.4, slides (from here) |
| 05-24 | SETH implies OVH, lower bound for LCS | slides (from here) |
| 05-26 | Cubic-time equivalence to APSP | slides (from here) |
| 05-31 | 3SUM revisited | slides (from here) |
| 06-02 | Lower bounds for decidability of arithmetic | Sipser |
| 06-07 | Lower bounds for decidability of arithmetic | Sipser |
| 06-09 | Lower bounds for decidability of arithmetic | Sipser |
| Final exam on Wednesday, June 14, 16:00~19:00 in classroom 1 (1101) | ||
There will be several homework assignments in this course. Homeworks must be turned in in English, and must be submitted on paper at the beginning of the lecture in the classroom.