BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:UW-Madison-Physics-Events
BEGIN:VEVENT
SEQUENCE:0
UID:UW-Physics-Event-1820
DTSTART:20100325T180000Z
DURATION:PT1H0M0S
DTSTAMP:20260422T131504Z
LAST-MODIFIED:20100322T115634Z
LOCATION:5310 Chamberlin
SUMMARY:Holographic Algorithms Capture Precisely Tractable Planar Coun
 ting Problems\, R. G. Herb Condensed Matter Seminar\, Jin-Yi Cai\, UW-
 Madison
DESCRIPTION:Counting type problems and their associated partition func
 tions have been studied from many interesting perspectives.<br>
\n<br>
 
\nIn the statistical physics community there is a long history of res
 earch on Exactly Solved Models (Fisher\, Temperley\, Kasteleyn\, C.N.Y
 ang\, Baxter\, Lieb\, ...). In the pure mathematics community Lovasz d
 efined the general graph homomorphism functions in 1967.<br>
\n<br>
\n
 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 solve
 d "exactly" on restricted classes of inputs. Fisher-Kasteleyn-Temperle
 y method is a famous example.<br>
\n<br>
\nAll these predate the moder
 n theory of computing\, which is now guided by the P and NP conjecture
 . In the language of computational complexity theory\, the FKT algorit
 hm is a polynomial time algorithm for counting the number of perfect m
 atchings for all planar graphs.<br>
\n<br>
\nIn this talk I report som
 e exciting new development\, coming from complexity theory. They give 
 fairly general answers\, in a provable sense\, to the venerable questi
 on: What "systems" can be solved "exactly" and what "systems" are "dif
 ficult". 
URL:https://www.physics.wisc.edu/events/?id=1820
END:VEVENT
END:VCALENDAR