Fine-grained analysis of algorithms is a highly active research topic. Recent results have provided (conditional) lower bounds for a variety of well-studied polynomial-time solvable problems. For example, dynamic programming algorithms for various string and sequence problems are essentially optimal unless there are breakthrough results for solving Satisfiability. Thus, fine-grained analysis provides much-needed explanatory power when „we“ are stuck with a certain running time.

In addition to signing up via basis please send an email to kratsch@cs.uni-bonn.de to provide your email address (using „[Fine-grained analysis of algorithms]“ as the subject). You will receive occasional notifications, access to scientific papers, and the exercise sheets via email/dropbox. Note that sending an email is not equivalent to signing up on basis and comes with no obligations.

Important: No lecture notes will be provided. Everything will be discussed at reasonable speed during the lectures. Additionally, there will be plenty of reading suggestions (papers are provided) and exercise tasks. Both will be supported by discussions and group work in the tutorials.

There will be an oral exam at the end of the term. The tentative dates are August 4 and September 12, 2017. There are no requirements for admittance and the final grade is determined solely by the exam.

In the tutorials you will be given time and support to solve exercises in teams of two and to read and discuss papers. Eva-Maria Hols will be present in tutorials and answer your questions, give hints, or join the discussion. There will be essentially no presentation of solved exercises since the focus is on solving things yourself. In particular, being able to explain a solution to your neighbor is highly beneficial, and being told that „this is actually quite easy“ is much more believable coming from your neighbor. We also found that (unsurprisingly?) students are much more apt at understanding one anothers problems with a task.

There will be a combination of exercise tasks and reading assignments that complement the current lecture content. The best form of participation is to read papers at home as far as possible respectively think a little about exercise tasks before then going to the tutorial to discuss and solve. We will not grade or proof-read your solutions, but you can verify your ideas by asking Eva-Maria during the tutorial.

There are no prerequisites other than having completed a Bachelor (typically in mathematics or computer science) or being close to doing so. Standard Bachelor lectures about algorithm design/analysis, discrete structures, logic, complexity are nevertheless beneficial.

If you do not have your Bachelor yet then you need contact the examination office to sign up for the lecture. You can still only use the grade for this course towards your Master degree.

There will be no lecture notes. The lecture will be given on the board at a reasonable speed, allowing also for discussion of the material.

Complementary reading in the form of scientific papers will be provided, but this cannot replace following the lecture material. If you miss a lecture, try to find someone who took notes.

1. Proving lower bounds for polynomial-time problems, i.e., what to do if our problem is not NP-hard but we are stuck at a still too slow running time: Try to prove that this is optimal after all modulo appropriate complexity assumptions.
2. The relevant complexity assumptions and the (limited) relations between them.
3. Some implications on lower bounds for NP-hard problems.
4. Adjacent topics such as adaptive algorithms will be covered as time permits.
5. Fine-grained complexity is a highly active topic and interesting results may appear during the course of the lecture. We will try to more or less spontaneously include such results.

There are unfortunately no books yet on this topic. Papers on particular results or surveys will be shared via dropbox. (Most papers are anyway accessible via the university network but this saves the hassle of searching yourself.)