I don't go to England much because they don't have many researchers in computational complexity, so I get a rare chance to talk to many of the researchers in this area. These workshops give us a chance for us to tell them about the latest in complexity and I can learn about areas I don't keep up with as much as I should.

Leslie Ann Goldberg gave a neat talk on the hardness of estimating the Tutte polynomial of graphs on a variety of points. I never really learned about the Tutte polynomial; it has some cool properties that for various parameters can count properties of graphs such as number of connected components. Goldberg and Mark Jerrum showed some of the approximations are #P-hard, that is hard for counting solutions of NP problems. We rarely see #P-hardness for approximating as all #P problems can be approximated probabilistically with an NP oracle. The Tutte polynomial is harder to approximate on some negative values because of the cancellations given by negative terms.

Are there any examples of deterministic approximation algorithms for #P-complete problems ?

ReplyDelete

ReplyDeleteAre there any examples of deterministic approximation algorithms for #P-complete problems ?Yes. Dror Weitz's paper in the last STOC gives the first(?) deterministic PTAS for a #P-complete problem. The paper also mentions another recent one.

--kunal

Caveat: A

ReplyDeletenatural#P-complete problem