Events

Events at Physics

<< Fall 2009 Spring 2010 Summer 2010 >>
Subscribe your calendar or receive email announcements of events
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
Add this event to your calendar