Archive for November, 2011
The talk that I gave at UMSL can now be downloaded here. This talk describes two different protocols for perfect simulation. The first, Partially Recursive Acceptance Rejection, gives an easy way to generate perfect samples from loosely coupled Markov random fields (such as the Ising model) in linear time without building a Markov chain at all for the problem.
The second part discusses Sequential Acceptance Rejection, a method that has proved useful for problems like approximating the permanent in dense problem instances.
Today I am giving the Algebra/Number Theory/Combinatorics Seminar at the Claremont Colleges. This talk, “What is a #P complete problem” is a prequel in a sense to an earlier talk I gave in the Seminar last year. In the earlier talk, I discussed new methods for approximating the permanent of a matrix. In this talk, I will argue that finding the permanent is a hard problem. One way to characterize hardness of a numerical problem is the notion of number P problems, or #P for short. I will define #P problems and give Ben-Dor and Halevi’s 1993 proof that finding the permanent of a matrix is a #P hard problem, so if we could solve it quickly, any problem in #P could also be solved quickly.