40 citations · 153 across the 24 of their papers we have counts for
7 papers · 1 filter
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…
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…
Affine reductions for LPs and SDPs
Gábor Braun, Sebastian Pokutta, Daniel Zink
We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical…
The matching polytope does not admit fully-polynomial size relaxation schemes
Gábor Braun, Sebastian Pokutta
The groundbreaking work of Rothvoß [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the…
Average case polyhedral complexity of the maximum stable set problem
Gábor Braun, Samuel Fiorini, Sebastian Pokutta
We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via linear programs (LPs), in two distinct models. In the uniform…
An algebraic approach to symmetric extended formulations
Gábor Braun, Sebastian Pokutta
Extended formulations are an important tool to obtain small (even compact) formulations of polytopes by representing them as projections of higher dimensional ones. It is an import…
Approximation Limits of Linear Programs (Beyond Hierarchies)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta +1
We develop a framework for approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields un…