Strong reductions for extended formulations (Q1801022): Difference between revisions

@@ Property / cites work @@
+Inapproximability of Combinatorial Problems via Small LPs and SDPs
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+Linear vs. semidefinite extended formulations
@@ Property / cites work: Linear vs. semidefinite extended formulations / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+Approximation Limits of Linear Programs (Beyond Hierarchies)
+Normal rank
@@ Property / cites work @@
+Approximate Constraint Satisfaction Requires Large LP Relaxations
+Normal rank
@@ Property / cites work @@
+Integrality gaps for Sherali-Adams relaxations
@@ Property / cites work: Integrality gaps for Sherali-Adams relaxations / rank @@
+Normal rank
@@ Property / cites work @@
+CSP gaps and reductions in the lasserre hierarchy
@@ Property / cites work: CSP gaps and reductions in the lasserre hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The stable set problem and the lift-and-project ranks of graphs
+Normal rank
@@ Property / cites work @@
+On a Representation of the Matching Polytope Via Semidefinite Liftings
+Normal rank
@@ Property / cites work @@
+Extension Complexity, MSO Logic, and Treewidth
@@ Property / cites work: Extension Complexity, MSO Logic, and Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Sparsest cut on bounded treewidth graphs
@@ Property / cites work: Sparsest cut on bounded treewidth graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Euclidean distortion and the sparsest cut
@@ Property / cites work: Euclidean distortion and the sparsest cut / rank @@
+Normal rank
@@ Property / cites work @@
+A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+Gadgets, Approximation, and Linear Programming
@@ Property / cites work: Gadgets, Approximation, and Linear Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
+Normal rank