Extension Complexity of Independent Set Polytopes
From MaRDI portal
Publication:4606697
DOI10.1137/16M109884XzbMath1416.90053arXiv1604.07062MaRDI QIDQ4606697
No author found.
Publication date: 9 March 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.07062
Related Items
Quasi-Popular Matchings, Optimality, and Extended Formulations, Regular Matroids Have Polynomial Extension Complexity, On the extension complexity of scheduling polytopes, Lifts for Voronoi cells of lattices, On permuting some coordinates of polytopes, On \(\epsilon\)-sensitive monotone computations, Extension Complexity of Independent Set Polytopes, Affine reductions for LPs and SDPs, Strengthening convex relaxations of 0/1-sets using Boolean formulas, Extension complexity of the correlation polytope, Extended formulations from communication protocols in output-efficient time, Lifting Theorems for Equality, Unnamed Item, Worst-case analysis of clique MIPs, Reflections on Proof Complexity and Counting Principles, MaxSAT Resolution and Subcube Sums, New limits of treewidth-based tractability in optimization
Cites Work
- Common information and unique disjointness
- On the nonnegative rank of distance matrices
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- On the extension complexity of combinatorial polytopes
- Expressing combinatorial optimization problems by linear programs
- A characterization of span program size and improved lower bounds for monotone span programs
- Complexity measures and decision tree complexity: a survey.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Some \(0/1\) polytopes need exponential size extended formulations
- A note on the extension complexity of the knapsack polytope
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Edge-Disjoint Paths in Expander Graphs
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Communication Complexity (for Algorithm Designers)
- Integer Programming
- The Pattern Matrix Method
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone circuits for matching require linear depth
- Lectures on Polytopes
- Interactive proofs and the hardness of approximating cliques
- Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
- Extension Complexity of Independent Set Polytopes
- The Matching Polytope has Exponential Extension Complexity
- Search Problems in the Decision Tree Model
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- The matching polytope does not admit fully-polynomial size relaxation schemes
- On the virtue of succinct proofs
- An information complexity approach to extended formulations
- Rectangles Are Nonnegative Juntas
- Extended formulations in combinatorial optimization
