181 citations · 620 across the 171 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013★ 10 cited
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…
cs.CC2013★ 20 cited
On the existence of 0/1 polytopes with high semidefinite extension complexity
Jop Briët, Daniel Dadush, Sebastian Pokutta
In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{Ω(n)…