Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n*n matrix A. The algorithm runs in O(n^2/eps^2) time, and approximates Per(A) t…