Dagstuhl Typecast

Nerd Shot from Dagstuhl Seminar 12421

Lance: Welcome to another Typecast from beautiful Schloss Dagstuhl. I’m here with Bill for the Workshop on Algebraic and Combinatorial Methods in Computational Complexity.

Bill: Beautiful? I thought this place was designed to be ugly so that we actually get work done.

Lance: So what work did you get done today, BIll?

Bill: I watched the debate. And you?

Lance: Steve Fenner and I came up with the easiest to describe PSPACE-complete problem ever!

Bill: Was it one of those poset things that you and Steve’s students work on.

Lance: A generalization of poset games but easier to describe. But we are getting off topic...

Bill: as did Obama and Mitt.

Lance: Bill my two minutes aren’t up yet. Anyway you’ll have to read about this new PSPACE-complete problem in a future post.

Bill: Since you didn’t ask, let me tell you about my favorite talk, Rank bounds for design matrices and applications by new Rutgers professor Shubhangi Saraf (Powerpoint). Despite the awful title

Lance: which is why I skipped that talk

Bill: it used complexity theory techniques to prove new things in math, a generalization of the Sylvester-Gallai theorem. You have n points on the plane...

Lance: Wait Bill, It will take longer to tell the S-G theorem than it would have to explain the new PSPACE-complete problem!

[Steve Fenner shows up with beer in hand. He goes off to get Lance one too.]

Bill: OK, I’ll leave this for a later post. What was your favorite talk?

Lance: Believe it or not it was an algorithms talk. Atri Rudra gave a very simple algorithm to do a join operation motivated by reconstructing 3-d collections of points from projections. [Powerpoint]

Bill: Yes, and it may have applications to complexity as most real world algorithms do.

[Steve arrives with Lance’s Beer. There is much happiness.]
Steve: My favorite talk so far was Rahul Santhanam’s [abstract] Reminded me of the good old days of complexity.

Lance: Let the guy give me beer and he thinks he can weasel his way into our typecast.

Bill: Lance, that’s how I got started in this business.

Lance: Rahul had some clever co-author, didn’t he?

Steve: No one important. Lance something?

Harry Buhrman: I like the GCT talk by Josh Grochow. [abstract]

Bill: In the future we’ll all have to learn GCT to get started in this field. I’m glad I’m living in the past. Lance, you paid me the highest compliment in my talk. You didn’t fall asleep and you even picked a fight with me.

Lance: Only because I had to stay awake to help the audience understand your confusing presentation.

Bill: It was only one slide.

Lance: It was only one fight.

Bill: I still feel as complimented as a bit that’s just been toggled .

Lance: I’m happy for you. Actually, it was not that bad a result. Now that’s my highest compliment.

Harry: Hey, this isn’t fair, we’ve haven’t heard all the talks yet.

[Both Harry and Steve are talking later tonight]

Lance: Life isn’t fair, get over it.

Bill: Let’s call it a day.

Lance: Watch my twitter feed later this week for a special musical complexity tribute.

Bill: I can’t wait.

Lance: So until next time, remember that in a complex world, best to keep it simple.