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

Fingerprint

Projection
Game
Graph in graph theory
Expander
Singular Values
Theorem
Decay
Generalise
Repetition

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Tulsiani, M., Wright, J., & Zhou, Y. (2014). Optimal strong parallel repetition for projection games on low threshold rank graphs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings (PART 1 ed., pp. 1003-1014). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1). Springer-Verlag. https://doi.org/10.1007/978-3-662-43948-7_83

Optimal strong parallel repetition for projection games on low threshold rank graphs. / Tulsiani, Madhur; Wright, John; Zhou, Yuan.

Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer-Verlag, 2014. p. 1003-1014 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1).

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

Tulsiani, M, Wright, J & Zhou, Y 2014, Optimal strong parallel repetition for projection games on low threshold rank graphs. in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 8572 LNCS, Springer-Verlag, pp. 1003-1014, 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Copenhagen, Denmark, 7/8/14. https://doi.org/10.1007/978-3-662-43948-7_83
Tulsiani M, Wright J, Zhou Y. Optimal strong parallel repetition for projection games on low threshold rank graphs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer-Verlag. 2014. p. 1003-1014. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-662-43948-7_83
Tulsiani, Madhur ; Wright, John ; Zhou, Yuan. / Optimal strong parallel repetition for projection games on low threshold rank graphs. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer-Verlag, 2014. pp. 1003-1014 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{d55e39ad1d6b4ab7a8408ff99e164a50,
title = "Optimal strong parallel repetition for projection games on low threshold rank graphs",
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.",
author = "Madhur Tulsiani and John Wright and Yuan Zhou",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/978-3-662-43948-7_83",
language = "English (US)",
isbn = "9783662439470",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
number = "PART 1",
pages = "1003--1014",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
edition = "PART 1",

}

TY - GEN

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

AU - Tulsiani, Madhur

AU - Wright, John

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84904200503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904200503&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-43948-7_83

DO - 10.1007/978-3-662-43948-7_83

M3 - Conference contribution

AN - SCOPUS:84904200503

SN - 9783662439470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1003

EP - 1014

BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings

PB - Springer-Verlag

ER -