Computational Complexity

Monday, August 16, 2004

 
Favorite Theorems: Parallel Repetition

Posted by Lance

July Edition

Consider a simple Arthur-Merlin game: Arthur probabilistically chooses a string r sends it to Merlin who responds with y and then Arthur runs some algorithm A(r,y) to decide whether to accept. Merlin's goal is to achieve the highest acceptance probability possible p for Arthur. Suppose we run the game twice in parallel, Arthur sends r₁ and r₂ and Merlin sends y₁ and y₂ and Arthur accepts if A(r₁,y₁) AND A(r₂,y₂). The highest possible acceptance probability will be p².

Now consider the MIP model with two Merlins M₁ and M₂ who cannot communicate with each other. Arthur sends u and v to M₁ and M₂ respectively who respond with y and z. Arthur accepts based on some function A(u,v,y,z). Once again M₁ and M₂ try to achieve the highest possible acceptance probability p. Now we run the game twice in parallel, Arthur sending u₁ and u₂ to M₁ and v₁ and v₂ to M₂ receiving y₁ and y₂ from M₁ and z₁ and z₂ from M₂ and accepting if A(u₁,v₁,y₁,z₁) AND A(u₂,v₂,y₂,z₂).

One might assume that the best the provers can achieve is p² (an assumption in fact made in an early paper co-authored by a certain weblog author) but in some circumstances the provers can do better. However Ran Raz shows that if p is less than 1, one can get an exponential decrease in p with a polynomial number of parallel rounds in

A Parallel Repetition Theorem by Ran Raz

This paper settles one of the more perplexing aspects of multiple prover proof systems with a highly complicated proof. The result also plays a critical role in reducing the number of queries in probabilistically checkable proof systems which led to some optimal approximation bounds.

As a side note I am off on vacation tomorrow and Adam Klivans will guest blog in my absence. Enjoy.

11:14 AM # 0 comments

Comment Feeds: This Post All