In the following paper
http://www.stat.uchicago.edu/~pmcc/reports/permanent.pdf
it is stated that:
"Exact computation of permanents of general matrices is a #P (sharp P) complete problem, so no deterministic polynomial-time algorithm is available. However, polynomial-time algorithms exist for certain special cases, such as general fixed-rank matrices (Barvinok 1996), and for approximate Monte-Carlo computation of general non-negative matrices (Jerum et al. 2004)."
I am a beginner in this field. So, can anybody comment on the algorithms mentioned in (Barvinok 1996) and about approximate Monte-Carlo computation in (Jerum et al. 2004)?
Moreover, can we think about fully polynomial-time randomized approximation scheme (FPRAS) to efficiently calculate permanents of a matrix?
The Monte=Carlo method is actually a FPRAS, at least according to my definition of FPRAS, so that is an example. Barvinok's algorithm is probably too hard to explain without a long answer and some higher level background math, but I do know that Barvinok came up with a (still farily complicated) way to count the number of integer points exactly in a convex polytope (bounded solution region to a system of linear inequalities) in polynomial time when the dimension of the polytope is fixed. So I'm assuming he is doing something related for the permanent, and that basically if the rank of the matrix is fixed this is like having "fixed true dimension" for a convex polytope, even if the polytope is embedded in a higher dimensional space. Barvinok is good at coming up with polynomial time algorithms when something like the "dimension" is fixed.