1 Search Results for "Schaffner, Christian"


Document
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case

Authors: Harry Buhrman, Serge Fehr, and Christian Schaffner

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value < 1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game G has a non-signaling value v_{ns}(G) < 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n. Stronger than that, we prove that the probability of winning more than (v_{ns}(G) + delta) * n parallel repetitions is exponentially small in n (for any delta > 0). Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.

Cite as

Harry Buhrman, Serge Fehr, and Christian Schaffner. On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 24-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2014.24,
  author =	{Buhrman, Harry and Fehr, Serge and Schaffner, Christian},
  title =	{{On the Parallel Repetition of Multi-Player Games: The No-Signaling Case}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{24--35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.24},
  URN =		{urn:nbn:de:0030-drops-48034},
  doi =		{10.4230/LIPIcs.TQC.2014.24},
  annote =	{Keywords: Parallel repetition, non-signaling value, multi-player non-local games}
}
  • Refine by Author
  • 1 Buhrman, Harry
  • 1 Fehr, Serge
  • 1 Schaffner, Christian

  • Refine by Classification

  • Refine by Keyword
  • 1 Parallel repetition
  • 1 multi-player non-local games
  • 1 non-signaling value

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail