Computational Complexity

Thursday, September 18, 2008

 
Dagstuhl Review

Posted by Lance

This week I'm at a Dagstuhl seminar on Computational Complexity of Discrete Problems, the end of summer trip for me as Northwestern's fall quarter classes start next week. Dagstuhl has changed in subtle ways (we get shampoo now) and there are far fewer computers in the computer room as many people now hide out in their rooms using wifi. There is a robot playing foosball table in the main hall that plays quite a mean game and a great diversion to us all. I do however miss the old Dagstuhl days when we were cut off from the world and all we did was drink and prove theorems and being blissfully unaware that, say, my country's economy is tanking.

A few years ago I discussed the problem of finding duplicates in a stream of numbers. Jaikumar Radhakrishnan gave a talk here showing how to find a duplicate in randomized poly-log space using only one pass through the data.

Also parallel repetition is making quite a comeback because of its connections to PCPs and the unique game conjecture. Raz recently showed limitations on parallel repetition, basically the error goes down at least quadratically as bad as you like. Thomas Holenstein talked about his proof that gives cubically as bad and Oded Regev talked about the general connections between unique games, parallel repetition and semidefinite programming relaxations.

These were just a taste of the interesting stuff discussed this week. Talks, abstracts, slides and more here.

2:40 AM # 0 comments

Comment Feeds: This Post All