Notes on Dagstuhl

A few notes on Dagshul which Lance and I were at last week.

1. I could tell you about the talks, but the website does a better job: here
2. I value going to talks more than Lance does, which is odd since he probably gets more out of them. Nevertheless, they serve two functions:
   1. Lets me know of new results or even areas I should look into (E.g. Chattopadhyay's talk on Linear Systems over Composite Moduli was news to me and is stuff I want to learn about.)
   2. Makes me feel guilty for not having already looked into an areas (E.g., Anna Gal's talk on Locally Decodable Codes reminded me that I really should learn or relearn some of that stuff and update my PIR website, Swastik's talk on parity quantifiers and graphs reminds me that I should read a book I've had on my shelf for about 10 years: The strange logic of Random Graphs by Joel Spencer.)
3. I thought that I was the only person going to both Dagstuhl and Ramsey Theory in Logic and ... so that I could give the same talk in both places. But Eli Ben-Sasson will be at both. But he missed my talk at Dagstuhl. He'll see a better version in Italy since I have made some corrections.
4. At Dagstuhl there is a book that people hand write their abstracts in. In this digital hardwired age do we need this? In case a Nuclear Bomb goes off and all information stored electronically are erased, we can rebuilt civilization based on those handwritten notebooks. The first thing people will want to know after they crawl out of their bomb shelters will be: is there an oracle separating BQP from PH. And Scott Aaronson's Handwritten abstract will tell them. (I hope his handwriting is legible.)
5. Peter Bro Miltersen gave an excellent talk. His open problems were very odd. He did NOT say I want to solve problem such-and-such. He instead said I want to find a barrier result to show that problem such-and-such is hard. It seems to me that one should really try hard to solve a problem before proving its hard. Then again, by trying to prove its hard he may solve it. I hope that if he solves it he won't be disappointed. Maybe his paper will be titled A proof that showing that problem such-and-such is hard is itself hard.
6. One odd benefit of being in Dagstuhl: I spend some time in the library reading articles that I really could have read at home, but somehow don't have time to. Here is one result I read about that I will blog about later: Let d be a distance. If you have n points in a circle of diameter 1 how many pairs of points are you guaranteed have distance \le d apart?
7. Next week I'll be in Italy and not posting, so you get Lance Fortnow all five days! Lets hope they are not all on P vs NP.