2 citations · 2 across the 2 of their papers we have counts for
6 papers · 1 filter
On Approximability of Satisfiable k-CSPs: V
Amey Bhangale, Subhash Khot, Dor Minzer
We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], w…
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…
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 tha…
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…
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…