Parallel Repetition of k-Player Projection Games

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with a value less than 1.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024
EditorsAmit Kumar, Noga Ron-Zewi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773485
DOIs
StatePublished - Sep 2024
Event27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024 - London, United Kingdom
Duration: Aug 28 2024Aug 30 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume317
ISSN (Print)1868-8969

Conference

Conference27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024
Country/TerritoryUnited Kingdom
CityLondon
Period8/28/248/30/24

Keywords

  • Multiplayer games
  • Parallel Repetition
  • Projection games

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Parallel Repetition of k-Player Projection Games'. Together they form a unique fingerprint.

Cite this