1 citations · 3 across the 4 of their papers we have counts for
5 papers · 1 filter
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Amey Bhangale, Mark Braverman, Subhash Khot +3
Let be a -player game with value , whose query distribution is such that no marginal on players admits a non-trivial Abelian embedding. We show that for…
Biased Linearity Testing in the 1% Regime
Subhash Khot, Kunal Mittal
We study linearity testing over the -biased hypercube in the 1% regime. For a distribution supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0…
On Approximability of Satisfiable -CSPs: VII
Amey Bhangale, Subhash Khot, Yang P. Liu +1
Let be finite alphabets, and let be a distribution over in which the probability of each atom is at least . We prove that if $…
On Approximability of Satisfiable -CSPs: VI
Amey Bhangale, Subhash Khot, Yang P. Liu +1
We prove local and global inverse theorems for general -wise correlations over pairwise-connected distributions. Let be a distribution over such that the…
Parallel Repetition for -Player XOR Games
Amey Bhangale, Mark Braverman, Subhash Khot +2
In a - game , the verifier samples a challenge where is a probability distribution over , and a map $t\colon Σ\ti…