193 citations · 549 across the 24 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
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.LG2015
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak, Ankur Moitra
In the noisy tensor completion problem we observe entries (whose location is chosen uniformly at random) from an unknown tensor . We assume that…
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…