License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.22
URN: urn:nbn:de:0030-drops-81670
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8167/
Go to the corresponding LIPIcs Volume Portal

Bavarian, Mohammad ; Vidick, Thomas ; Yuen, Henry

Parallel Repetition via Fortification: Analytic View and the Quantum Case

pdf-format:
LIPIcs-ITCS-2017-22.pdf (0.7 MB)

Abstract

In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings.

First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest.

An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

BibTeX - Entry

@InProceedings{bavarian_et_al:LIPIcs:2017:8167,
  author =	{Mohammad Bavarian and Thomas Vidick and Henry Yuen},
  title =	{{Parallel Repetition via Fortification: Analytic View and the Quantum Case}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{22:1--22:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8167},
  URN =		{urn:nbn:de:0030-drops-81670},
  doi =		{10.4230/LIPIcs.ITCS.2017.22},
  annote =	{Keywords: Parallel repetition, quantum entanglement, non-local games}
}

Keywords: Parallel repetition, quantum entanglement, non-local games
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI