# 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

First lecture: Tue, Apr 19

### Lecturer

**Prof. Dr. Markus Bläser**, Email: mblaeser at cs.uni-saarland...

Office Hours: whenever my office door is open, E 1 3, Room 412

### Grading

Oral exams at the end of the semester.