38 citations · 171 across the 26 of their papers we have counts for
3 papers · 2 filters
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…
The matching problem has no small symmetric SDP
Gábor Braun, Jonah Brown-Cohen, Arefin Huq +5
Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß recently proved that any, not necessarily symmetric, linear program also has exp…
Combinatorial Optimization Algorithms via Polymorphisms
Jonah Brown-Cohen, Prasad Raghavendra
An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, th…