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 r1 and r2 and Merlin sends y1 and y2 and Arthur accepts if A(r1,y1) AND A(r2,y2). The highest possible acceptance probability will be p2.
Now consider the MIP model with two Merlins M1 and M2 who cannot communicate with each other. Arthur sends u and v to M1 and M2 respectively who respond with y and z. Arthur accepts based on some function A(u,v,y,z). Once again M1 and M2 try to achieve the highest possible acceptance probability p. Now we run the game twice in parallel, Arthur sending u1 and u2 to M1 and v1 and v2 to M2 receiving y1 and y2 from M1 and z1 and z2 from M2 and accepting if A(u1,v1,y1,z1) AND A(u2,v2,y2,z2).
One might assume that the best the provers can achieve is p2 (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
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.
No comments:
Post a Comment