Optimal strong parallel repetition for projection games on low threshold rank graphs

Madhur Tulsiani, John Wright, Yuan Zhou

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

Abstract

Given a two-player one-round game G with value val(G) = (1 - η), how quickly does the value decay under parallel repetition? If G is a projection game, then it is known that we can guarantee val(G ⊗n ) ≤ (1 - η 2 ) Ω(n) , and that this is optimal. An important question is under what conditions can we guarantee that strong parallel repetition holds, i.e. val(G ) ≤ (1 - η) Ω(n) ? In this work, we show a strong parallel repetition theorem for the case when G's constraint graph has low threshold rank. In particular, for any k ≥ 2, if σ k is the k-th largest singular value of G's constraint graph, then we show that val(G ⊗n ) ≤(1-√1-σ k 2 / k·η) Ω(n) . This improves and generalizes upon the work of [RR12], who showed a strong parallel repetition theorem for the case when G's constraint graph is an expander.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer-Verlag
Pages1003-1014
Number of pages12
EditionPART 1
ISBN (Print)9783662439470
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
CountryDenmark
CityCopenhagen
Period7/8/147/11/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal strong parallel repetition for projection games on low threshold rank graphs'. Together they form a unique fingerprint.

Cite this