Technical Program

Paper Detail

Paper Title A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem
Paper IdentifierTU2.R7.3
Authors Himanshu Tyagi, Indian Institute of Science, India; Shun Watanabe, Tokyo University of Agriculture and Technology, Japan
Session Game Theory
Location Bièvre, Level 5
Session Time Tuesday, 09 July, 11:40 - 13:00
Presentation Time Tuesday, 09 July, 12:20 - 12:40
Manuscript  Click here to download the manuscript
Abstract We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced recently for proving strong converse results in multiuser information theory and entails a change of measure after replacing hard information constraints with soft ones.