### 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 language | English (US) |
---|---|

Title of host publication | Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings |

Publisher | Springer-Verlag |

Pages | 1003-1014 |

Number of pages | 12 |

Edition | PART 1 |

ISBN (Print) | 9783662439470 |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

Event | 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark Duration: Jul 8 2014 → Jul 11 2014 |

### Publication series

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

Number | PART 1 |

Volume | 8572 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Denmark |

City | Copenhagen |

Period | 7/8/14 → 7/11/14 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -