We prove a generalization of Raz's Lemma to random processes thatallows us to improve the analysis of the reduction of Håstad etal. in the public-coin case to$1-\gamma-O(\sqrt{-\logg{\epsilon}/\reps})$, i.e., we remove thedependence on the number rounds completely, and thus the restrictionto settings where $\reps>\exchanges^2$.
An important implication of the strengthened parallel repetitiontheorem is the first efficient \emph{concurrent} repetition theoremfor protocols with a non-constant number of rounds. In concurrentrepetition, the verifiers execute completely independently and onlyreport their final decision, i.e., the prover chooses arbitrarily inwhich order it interacts with the individual verifiers. This shouldbe contrasted with parallel repetition where the verifiers aresynchronized in each round.
Category / Keywords: foundations / parallel repetition Date: received 13 Jul 2009 Contact author: dog at csc kth se Available format(s): PDF | BibTeX Citation Note: This is a preliminary version. All comments are most welcome!The cited manuscript of Hastad et al. (2008) should be posted shortly.
Version: 20090718:044300 (All versions of this report) Short URL: ia.cr/2009/347 Discussion forum: Show discussion | Start new discussion