Complexity of Polynomial-Time Problems
(Komplexität von Polynomialzeitproblemen)
| Instructor: | Sebastian Krinninger |
| Type: | 2VO + 1PS |
| ECTS: | 2.5 + 2.5 |
| Curriculum: | WFM Master Informatik |
| Schedule VO: | Thursday, 14:00-15:35, T.04 |
| Schedule PS: | Monday, 14-15:30, T.05 (biweekly) |
| First meeting: | Thursday, 05.10. |
| Prerequisites: | Basic courses on Algorithms and Data Structures, |
| and Complexity Theory | |
| Registration: | PLUS online: VO PS |
Description
Complexity theory traditionally analyzes if a problem can be solved in polynomial-time (by providing an efficient algorithm) or if the problem is NP-hard (by providing a reduction). For practical purposes however the label "polynomial-time" is too coarse: in big-data applications, it makes a huge difference whether an algorithm runs in say linear, quadratic, or cubic time. The latter is often deemed "intractable" despite being in polynomial time. In this course we explore an emerging subfield at the intersection of complexity theory and algorithm design which aims at a more fine-grained view of the complexity of polynomial-time problems. We present a mix of upper and lower bounds for fundamental poynomial-time solvable problems, often by drawing interesting connections between seemingly unrelated problems. A prototypical result presented in this course is the following: there is no algorithm for computing the longest common subsequence of two strings that is substantially faster than the simple dynamic programming algorithm, unless we find a substantially faster algorithm for SAT solving. The techniques for proving such statements have been developed in recent years and this course is thus very close to state-of-the-art research.
Organization
The VO part of this course (2 hrs/week, 2.5 ECTS) consists of weekly blackboard lectures, each taking 90 minutes. At the end of the semester there will be a written final exam. The PS part of this course (1 hr/week, 2.5 ECTS) consists of biweekly exercise sessions, each taking 90 minutes. Your task here will be to solve exercise problems beforehand and then present the solutions to each other. The exam problems will be similar in style to the exercises. You can earn bonus points for the final exam (up to 10% of the total number of points) by being a scribe during one of the lectures.
Rules for Excercise Sessions (PS)
There will be five exercise sheets and you will have at least 10 days to work on each exercise sheet. Each exercise sheet has the same contribution to your final grade. You are required to email your solutions to me as a pdf file the day before the corresponding exercise session takes place. You are allowed to collaborate, but you have to write down a solution on your own, using your own words. Indicate the names of your collaborators for each exercise you solve. Further, cite all external sources that you use (books, websites, research papers, etc.). We will discuss the solutions the the exercise problems during the biweekly exercise session. Attendance to exercise sessions is mandatory by university regulations. Your are required to present one of your solutions at least once during the whole course (but the quality and correctness of your presentation will not further influence your grade). Apart from this requirement, your grade is solely determined by the quality your submitted solutions. In addition to the exercise session, there will be two Q&A sessions where you can ask questions about the material presented in class. You need to collect at least 50 % of the points of the exercise sheets to pass this part of the course. The grading scheme is as follows: 100% - 87,5%: 1; 87,5% - 75%: 2; 75% - 62,5%: 3; 62,5% - 50%: 4; <50%: 5.
Schedule (tentative) and Material
| Date | VO/PS | Topic | Material | Literature |
|---|---|---|---|---|
| Thu, 05.10. | VO | Introduction, Orthogonal Vectors and Diameter | notes board (old) slides | [Roditty, V. Williams '13] Video by V. Williams |
| Thu, 12.10. | VO | Hardness from Strong Exponential Time Hypothesis | notes board (old) slides | [Williams '04] Video by V. Williams |
| Mon, 23.10. | VO | Hardness of Longest Common Subsequence | notes (old) slides | [Bringmann/Künnemann '15] [Abboud et al. '15] Video by V. Williams |
| Mon, 06.11. | PS | Discussion of Exercise Sheet 1 (*) | sheet 1 (source) | |
| Thu, 09.11. | VO | Subcubic Equivalences Between Path and Triangle Problems | notes board (old) slides | [Williams, V. Williams '10] Video by V. Williams |
| Mon, 13.11. | PS | Q&A Session | ||
| Thu, 16.11. | VO | More on Subcubic Equivalences | notes (old) slides | [Williams, V. Williams '10] [Abboud et al. '15] Video by V. Williams |
| Mon, 20.11. | PS | Discussion of Exercise Sheet 2 (*) | sheet 2 (source) | |
| Thu, 23.11. | VO | Boolean Matrix Multiplication I | notes board (old) slides (old) slides | |
| Thu, 30.11. | VO | Boolean Matrix Multiplication II | notes (old) slides | [Czumaj, Lingas '07] |
| Mon, 04.12. | PS | Discussion of Exercise Sheet 3 (*) | sheet 3 (source) | |
| Thu, 07.12. | VO | 3SUM Upper Bounds | notes (old) slides | [Grønlund, Pettie '14] |
| Thu, 14.12. | VO | 3SUM Hardness | notes (old) slides | [Gajentaan, Overmars '95] [Baran et al. '05] |
| Mon, 18.12. | PS | Discussion of Exercise Sheet 4 (*) | sheet 4 (source) | |
| Thu, 21.12. | VO | Convolution 3SUM | notes (old) slides | [Pătrașcu '10] [Williams, V. Williams '09] Video by V. Williams |
| Thu, 11.01. | VO | Nondeterministic Strong Exponential Time Hypothesis | notes (old) slides | [Carmosino et al. '16] Video by Schneider |
| Mon, 15.01. | PS | Discussion of Exercise Sheet 5 (*) | sheet 5 (source) | |
| Thu, 18.01. | VO | Faster APSP via Polynomial Method I | (old) slides | [Williams '14] |
| Thu, 25.01. | VO | Faster APSP via Polynomial Method II | (old) slides | [Williams '14] |
| Mon, 29.01. | PS | Q&A Session |
(*) Attendance mandatory
Exam
The exam takes place on February 12, 3-5 pm.
Literature
As the ideas and results presented in this course are quite new, there is unfortunately no textbook covering the topics of this course yet. The blackboard presentation will cover all material relevant for the exam. In addition, pointers to research papers as well as to slides of a previous iteration of this course will be provided.
A mini-course given by Virginia Vassilevska Williams at the Simons Institute for the Theory of Computing is available on Youtube: Session 1 Session 2 Session 3 Session 4