Dagstuhl Day One

The talks Monday were after my own heart. The day started with relativization: The always entertaining Scott Aaronson talked on his approach to get an oracle where BQP is not in the polynomial-time hierarchy. He gets some partial progress and a new conjectured language for separation, something he called Fourier checking.

Valentine Kabanets followed up talking about his work with Impagliazzo and Kolokolova giving a new axiomatic characterization of relativization. In my (seemingly minority) opinion, the number of tools we have that don't relativize are pretty slim and and traditional oracle models tell us plenty about what we can't do.

Fabian Wagner described his log-space algorithm for checking whether two planar graphs are isomorphic. Rahul Santhanam talked about our work (with Harry Buhrman) on the lower bounds we proved at last year's Dagstuhl. I talked about applications of computational complexity to economics and why everyone should walk from the Complexity Conference across the street to Electronic Commerce next summer and see for themselves.

But the best part of Dagstuhl are the open time where we meet and socialize over coffee, or wine and beer and discuss problems, struggle over old questions and try to prove new ones. That's the magic of Dagstuhl.