School Seminars and Colloquia

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


by Reuven Rubinstein

Institution: Faculty of Industrial Engineering and Management, Technion
Date: Fri 8th September 2006
Time: 3:15 PM
Location: Theatre 1, Ground Floor, 111 Barry Street, Carlton

Abstract: We present a new generic randomized algorithm for approximating quite general P-complete counting problems, like 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) method 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 and speed of 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 network.
For more details see our homepage and for wikipedia - the cross-entropy method.

For More Information: Emma Lockwood Tel: +61 3 8344 1617