After successful completion of the course, students are able to follow current developments in the research on algorithms and complexity, building on existing knowledge to algorithms and data structures and tying in with complexity theory and various application domains (e.g. network design, geometric problems, algorithms on planar graphs.) Students will be able to - explain notions and basic problems from the course; - describe formally and explain intuitively fine-grained complexity assumptions and their consequences; - describe formally and intuitively, analyze and prove properties of algorithms for selected hard problems; - design and analyze their own algorithms for unknown algorithmic problems using techniques from the course; - describe and explain the frontiers of current results in algorithms and complexity - gain understanding of current results and their context on their own.
The course addresses recent developments in algorithms research, their context within existing literature and the frontiers of current knowledge. Topics include (for example): - Basics of complexity theory (recap of NP-hardness, reductions) - Fine-grained complexity analysis under additional hypotheses, e.g. (strong) exponential-time hypothesis - Hard problems from logics (e.g. lower and upper bounds for the Boolean satisfiability problem) - General algorithmic techniques (subset convolutions, inclusion-exclusion, polynomial formulations) and their applications (e.g. Steiner trees) - Results on non-reducibility of certain problems - Hard problems on planar graphs in subexponential time (if time permits) - Hard geometric problems in subexponential time (if time permits)
The course is held in blocked lectures covering topics at the frontierof algorithms and complexity research. They take place in a seminar-like setting and are interactive, so students are expected to engage in classroom discussion. Every technique introduced in the course is demonstrated on several examples.
The grade is based on a short oral exam on the topics covered by the course. The students are allowed to choose one topic to focus on during the exam. In particular, the exam can also be taken in the form of a presentation of a current research article covering a topic from the course.