Extension complexity of independent set polytopes
From MaRDI portal
Publication:4606697
Abstract: We exhibit an -node graph whose independent set polytope requires extended formulations of size exponential in . Previously, no explicit examples of -dimensional -polytopes were known with extension complexity larger than exponential in . Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.
Recommendations
Cites work
- A characterization of span program size and improved lower bounds for monotone span programs
- A note on the extension complexity of the knapsack polytope
- An information complexity approach to extended formulations
- An information statistics approach to data stream and communication complexity
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Boolean function complexity. Advances and frontiers.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Common information and unique disjointness
- Communication Complexity
- Communication complexity (for algorithm designers)
- Communication lower bounds via critical block sensitivity
- Complexity measures and decision tree complexity: a survey.
- Edge-disjoint paths in expander graphs
- Exponential lower bounds for polytopes in combinatorial optimization
- Expressing combinatorial optimization problems by linear programs
- Extended formulations in combinatorial optimization
- Extension complexity of independent set polytopes
- Integer Programming
- Interactive proofs and the hardness of approximating cliques
- Lectures on Polytopes
- Lower bounds on the size of semidefinite programming relaxations
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone circuits for matching require linear depth
- On the nonnegative rank of distance matrices
- On the virtue of succinct proofs
- Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
- Rectangles are nonnegative juntas
- Search Problems in the Decision Tree Model
- Some \(0/1\) polytopes need exponential size extended formulations
- The matching polytope does not admit fully-polynomial size relaxation schemes
- The pattern matrix method
Cited in
(41)- Extension complexity of stable set polytopes of bipartite graphs
- Maximum semidefinite and linear extension complexity of families of polytopes
- Affine reductions for LPs and SDPs
- Subgraph polytopes and independence polytopes of count matroids
- Extended formulations for vertex cover
- Worst-case analysis of clique MIPs
- New limits of treewidth-based tractability in optimization
- On \(\epsilon\)-sensitive monotone computations
- Strengthening convex relaxations of 0/1-sets using Boolean formulas
- Extension complexity of the correlation polytope
- On the linear extension complexity of stable set polytopes for perfect graphs
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Parameterized extension complexity of independent set and related problems
- Some \(0/1\) polytopes need exponential size extended formulations
- On the extension complexity of scheduling polytopes
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Average case polyhedral complexity of the maximum stable set problem
- Tropical lower bound for extended formulations. II: Deficiency graphs of matrices
- Extension complexity, MSO logic, and treewidth
- Extended formulations for independence polytopes of regular matroids
- Extension complexity of independent set polytopes
- Small extended formulation for knapsack cover inequalities from monotone circuits
- Reflections on Proof Complexity and Counting Principles
- Quasi-popular matchings, optimality, and extended formulations
- Regular matroids have polynomial extension complexity
- Lifting Theorems for Equality
- Expanding operators for the independent set problem
- Extension complexity, MSO logic, and treewidth
- MaxSAT Resolution and Subcube Sums
- Lifts for Voronoi cells of lattices
- On the extension complexity of polytopes separating subsets of the Boolean cube
- On permuting some coordinates of polytopes
- Face enumeration for split matroid polytopes
- A topological version of Schaefer's dichotomy theorem
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- Sublinear extensions of polygons
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- Can you link up with treewidth?
- Can you link up with treewidth?
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
- Extension complexity of formal languages
This page was built for publication: Extension complexity of independent set polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606697)
