Paper Info
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-eta), 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(circle times n)) <= (1 -eta(2))(Omega(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(circle times)) <= (1 - eta)(Omega(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 sigma(k) is the k-th largest singular value of G's constraint graph, then we show that val(G(circle times n)) <= (1 - root 1-sigma(2)(k) / k .eta)(Omega(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.
Year
Venue
Field
2014
Lecture Notes in Computer Science
Discrete mathematics,Graph,Combinatorics,Constraint graph,Mathematics
DocType
Volume
ISSN
Conference
8572
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Madhur Tulsiani135824.60
John Wright2394.22
Yuan Zhou329028.29