Complexity and Randomness

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). For example Colin McDiarmid talked about the maximum degree of a random planar graph (Θ(log n)) and Mark Jerrum on Monte Carlo mixing methods, in addition to Irit Dinur on her PCP proof, Oded Goldreich on pseudorandomness and coming up Luca Trevisan on Gowers uniformity and Vijay Vazirani on markets.

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.