Holant problems, CSP and graph homomorphisms---An overview
Jin-Yi Cai
CS, UW Madison
Monday, September 14, 2009
4:00 PM, 4310 CS
I would like to give an informal overview of work we have done with colleagues including Xi Chen, Michael Kowalczyk, Pinyan Lu, Mingji Xia etc on the complexity of counting problems.
There is a substantial body of work, and we have seen some spectacular progress in recent years. It seems that there are now more tools available to tackle counting problems (P vs #P) than for decision problems (P vs NP.) Several new techniques have been developed, mainly of an algebraic nature. One is holographic reductions. Another is further development of the interpolation technique originally by Valiant. A yet another powerful technique is relating the problem to the tools from universal algebra (a la Butalov).
This talk will be an overview of our program. All graduate students are especially welcome; I will attempt to make it easy to understand. If there is sufficient interest I can continue with more technical talks in the sequel. (I will give a Departmental Colloquium in Math on Sept 25, at 4pm Van Vleck B239,
http://www.math.wisc.edu/~stpaul/colloquia.html and a Number Theory seminar Oct. 1, at 2:30pm, Van Vleck B131. http://www.math.wisc.edu/~masr/Fall2009.html)
Additional CS events.
|
