6 citations · 14 across the 11 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2019
Extended Formulation Lower Bounds for Refuting Random CSPs
Jonah Brown-Cohen, Prasad Raghavendra
Random constraint satisfaction problems (CSPs) such as random -SAT are conjectured to be computationally intractable. The average case hardness of random -SAT and other CSPs…
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…