6 citations · 14 across the 11 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
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…
cs.CC2015
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…