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 www.cemethod.org
Slides are available at:
http://iew3.technion.ac.il/Home/Users/ierrr01/talk-minxent05.pdf