QLunch: Towards understanding the algorithmic complexity of calculating the Ising partition function

Speaker: Martin Loebl, Charles University, Prague

Title: Towards understanding the algorithmic complexity of calculating the Ising partition function

Abstract:The Kasteleyn theory provides a way to calculate the Ising partition function of a finite graph, or equivalently, the generating function of the edge-cuts of the graph. In particular it also determines the size of the maximum cut.

I will speak about relations of the Kasteleyn theory and the complexity of algorithms. The main question is: Do the algorithms provided by the Kasteleyn theory have the lowest possible complexity?

I will present very modest results supporting the YES answer: the determination of the additive determinantal complexity of the Ising partition function (joint work with Masbaum) and relation with the Exponential Time Hypothesis.