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 is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)?
ds.algorithms
What abouthttp://portal.acm.org/citation.cfm?doid=1008731.1008738?If you are looking for exact algorithms, the only speedup I'm aware of ishttp://www.springerlink.com/content/ar7jwwy01qleny8e/fulltext.pdfWhich also can be used to show you can do c^n time for c<2 for sparse 0/1 matrices or the UP-hard mod 3 permanent.