TY - GEN

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

AU - Tulsiani, Madhur

AU - Wright, John

AU - Zhou, Yuan

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

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

T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

Y2 - 8 July 2014 through 11 July 2014

ER -