193 citations · 549 across the 24 of their papers we have counts for
Showing 2015 · cs.CCShow all
2 papers · 2 filters
cs.CC2015★ 8 cited
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…
cs.CC2015
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari
We prove that for every and predicate that supports a pairwise independent distribution, there exists an instance of the $\math…