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

The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS. 

However Dense versions of Max Cut do have a PTAS! 

This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up. 

Does such a speedup exists in the complexity literature?

Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable!
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.