Computational Complexity

Tuesday, August 29, 2006

 
Parallel Repetition Redux

Posted by Lance

This week I return to Banff for Recent Advances in Computational Complexity. The mountains help attract quite an impressive collection of fellow complexity theorists.

Last night Paul Beame presented a new paper by Thomas Holenstein that simplifies and improves part of Ran Raz's proof of the Parallel Repetition Theorem, one of the more complicated arguments in computational complexity. The new result replaces roughly Section 6 of Raz's paper with a new embedding argument (Holenstein's Lemma 8), a way for two players to usually agree on the outcome of a distribution where they both have approximations of the distribution, using only shared randomness and no other communication.

Paul did take nearly an hour sketching Raz's proof (with a little help from Ran who was in the audience) before he could even describe Holenstein's contribution so we don't yet have a simple version of the parallel repetition theorem, but it has become much simpler than before.

8:21 AM # 1 comments

1.  Anonymous says:  
   
   And Holenstein's proof also considers the no-signalling case, although you can proof the no-signalling case using Raz's proof too.
   

   9:47 AM, August 29, 2006

Comment Feeds: This Post All