12 citations · 21 across the 17 of their papers we have counts for
16 papers · 1 filter
Optimal Inapproximability of Generalized Linear Equations over a Finite Group
Amey Bhangale, Yezhou Zhang
Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to f…
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…
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…
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…