In the simultaneous message model, two parties holding n-bit integers
x,y send messages to a third party, the {\it referee}, enabling
him to compute a boolean function f(x,y). Buhrman et al
[BCWW01] proved the remarkable result that, when f is the
equality function, the referee can solve this problem by ...
more >>>
Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:
1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, n-fold parallel repetition ... more >>>