Other Event

How Many Needles are in a Haystack, or how to Solve #P-Complete Counting Problems Fast

Reuven Rubinstein (Technion)

Wednesday, July 19, 2006
2:00pm - 3:00pm
2717 IOE

Add to Google Calendar
This IOE talk may be of special interest to computer scientists.

About the Event

We present a new generic randomized algorithm for approximating quite general #P-complete counting problems, like satisfiability, the number of Hamiltonian cycles in a graph, the permanent, and the number of self-avoiding walks of certain length. To do so we cast the underlying counting problem into an associate rare-event probability estimation one, and then apply the cross-entropy (CE) and the MinxEnt methods for updating the parameters of the importance sampling (IS) distribution. We use importance sampling to speed up the simulation process and, thus to produce a low variance estimate of the desired counting quantity. We establish convergence of our algorithm for some particular #P-complete counting problems and present supportive numerical results, which strongly suggest that the presented algorithm has polynomial complexity in the size of the problem.

Additional Information

Contact: Prof. Robert Smith (IOE)

Email: rlsmith@umich.edu

Sponsor(s): IOE dept

Open to: Public