A Monte-Carlo Algorithm for Estimating the Permanent

Let A be an n x n matrix with 0-1 valued entries, and let per (A) be the permanent of A. We describe a Monte-Carlo algorithm which produces a - good in the relative sense - estimate of per(A) and has running time poly(n)2 sup n/2, where poly(n) denotes a function that grows polynomially with n.