2 citations · 5 across the 7 of their papers we have counts for
5 papers · 1 filter
Reasonable Bounds for Combinatorial Lines of Length Three
Amey Bhangale, Subhash Khot, Yang P. Liu +1
We prove that any subset with contains a combinatorial line of length , i.e., , not all equal, with…
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…