14 citations · 56 across the 7 of their papers we have counts for
4 papers · 1 filter
Sum of squares lower bounds for refuting any CSP
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell +1
Let be a nontrivial -ary predicate. Consider a random instance of the constraint satisfaction problem on variables with cons…
Lower bounds for CSP refutation by SDP hierarchies
Ryuhei Mori, David Witmer
For a -ary predicate , a random instance of CSP with variables and constraints is unsatisfiable with high probability when . The natural algorithmic tas…
How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
Let be a -ary predicate over a finite alphabet. Consider a random CSP instance over variables with constraints. When the instance will be unsa…
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…