What is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)?
What about

http://portal.acm.org/citation.cfm?doid=1008731.1008738

?

If you are looking for exact algorithms, the only speedup I'm aware of is

http://www.springerlink.com/content/ar7jwwy01qleny8e/fulltext.pdf

Which also can be used to show you can do c^n time for c&lt;2 for sparse 0/1 matrices or the UP-hard mod 3 permanent.