Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Holographic algorithms

Prof. Dr. Markus Bläser

News

No lecture on July 12!!!

Topic

While it is easy to decide whether a graph has a perfect matching, it is supposed to be a hard problem to count the number of perfect matchings in a graph. This is a classical result by Valiant. However, in planar graphs, it is easy to count the number of perfect matchings by the classical Fisher-Kasteleyn-Temperley algorithm. 3 decades after proving the hardness of counting perfect matchings in general graphs, Valiant proposed an amazingly simple idea to make use out of the Fisher-Kastelyn-Temperley algorithm by so-called holographic reductions. We start with learning the FKT-algorithm and then learn the important ideas of holographic reductions and algorithms.

(Caveat: This course has nothing to do with computer graphics and very little with physics!!)

Time & Date

Tue, 10:15 to 12:00, seminar room 16 in E1.3
First lecture: Tue, Apr 19

Lecturer

Grading

Oral exams at the end of the semester.

Assignments

Script