401 citations · 1.3k across the 12 of their papers we have counts for
Showing 2015 · cs.CCShow all
2 papers · 2 filters
cs.CC2015
Strong reductions for extended formulations
Gábor Braun, Sebastian Pokutta, Aurko Roy
We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from [arXiv:1410.8816] in two ways 1) relaxing the requirement of affine…
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…