#### Other Event

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

Add to Google Calendar

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

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.