## Events at Physics |

**R. G. Herb Condensed Matter Seminar**

**Holographic Algorithms Capture Precisely Tractable Planar Counting Problems**

**Date:**

**Thursday, March 25th**

**Time:**1:00 pm

**Place:**5310 Chamberlin

**Speaker:**Jin-Yi Cai, UW-Madison

**Abstract:**Counting type problems and their associated partition functions have been studied from many interesting perspectives.

In the statistical physics community there is a long history of research on Exactly Solved Models (Fisher, Temperley, Kasteleyn, C.N.Yang, Baxter, Lieb, ...). In the pure mathematics community Lovasz defined the general graph homomorphism functions in 1967.

There is a general sense that certain "systems" can be solved "exactly", while others are "difficult". There is also tremendous interest in certain "systems" which are "difficult" in general, but can be solved "exactly" on restricted classes of inputs. Fisher-Kasteleyn-Temperley method is a famous example.

All these predate the modern theory of computing, which is now guided by the P and NP conjecture. In the language of computational complexity theory, the FKT algorithm is a polynomial time algorithm for counting the number of perfect matchings for all planar graphs.

In this talk I report some exciting new development, coming from complexity theory. They give fairly general answers, in a provable sense, to the venerable question: What "systems" can be solved "exactly" and what "systems" are "difficult".

**Host:**Susan Coppersmith