Exponential Lower Bounds for Polytopes in Combinatorial Optimization (Q2796404): Difference between revisions

@@ Property / OpenAlex ID @@
+W1755753347
@@ Property / OpenAlex ID: W1755753347 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.0837
@@ Property / arXiv ID: 1111.0837 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for Local Search by Quantum Arguments
+Normal rank
@@ Property / cites work @@
+Lattice problems in NP ∩ coNP
@@ Property / cites work: Lattice problems in NP ∩ coNP / rank @@
+Normal rank
@@ Property / cites work @@
+On the extension complexity of combinatorial polytopes
+Normal rank
@@ Property / cites work @@
+Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
+Normal rank
@@ Property / cites work @@
+A lift-and-project cutting plane algorithm for mixed 0-1 programs
+Normal rank
@@ Property / cites work @@
+Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
+Normal rank
@@ Property / cites work @@
+Approximation Limits of Linear Programs (Beyond Hierarchies)
+Normal rank
@@ Property / cites work @@
+Average case polyhedral complexity of the maximum stable set problem
+Normal rank
@@ Property / cites work @@
+Information-theoretic approximations of the nonnegative rank
+Normal rank
@@ Property / cites work @@
+Common information and unique disjointness
@@ Property / cites work: Common information and unique disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+An information complexity approach to extended formulations
+Normal rank
@@ Property / cites work @@
+On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
+Normal rank
@@ Property / cites work @@
+Q3002766
@@ Property / cites work: Q3002766 / rank @@
+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 @@
+Extended formulations in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+The cut polytope and the Boolean quadric polytope
@@ Property / cites work: The cut polytope and the Boolean quadric polytope / rank @@
+Normal rank
@@ Property / cites work @@
+Geometry of cuts and metrics
@@ Property / cites work: Geometry of cuts and metrics / rank @@
+Normal rank
@@ Property / cites work @@
+Extended formulations, nonnegative factorizations, and randomized communication protocols
+Normal rank
@@ Property / cites work @@
+Q2934582
@@ Property / cites work: Q2934582 / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial bounds on nonnegative rank and extended formulations
+Normal rank
@@ Property / cites work @@
+Generalized probabilistic theories and conic extensions of polytopes
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
+Normal rank
@@ Property / cites work @@
+Optimal Sherali-Adams Gaps from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Theta Bodies for Polynomial Ideals
@@ Property / cites work: Theta Bodies for Polynomial Ideals / rank @@
+Normal rank
@@ Property / cites work @@
+Lifts of Convex Sets and Cone Factorizations
@@ Property / cites work: Lifts of Convex Sets and Cone Factorizations / rank @@
+Normal rank
@@ Property / cites work @@
+A counterexample to the Alon-Saks-Seymour conjecture and related problems
+Normal rank
@@ Property / cites work @@
+Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
+Normal rank
@@ Property / cites work @@
+Symmetry Matters for the Sizes of Extended Formulations
+Normal rank
@@ Property / cites work @@
+A short proof that the extension complexity of the correlation polytope grows exponentially
+Normal rank
@@ Property / cites work @@
+A new polynomial-time algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+Exponential lower bound for 2-query locally decodable codes via a quantum argument
+Normal rank
@@ Property / cites work @@
+Q3050157
@@ Property / cites work: Q3050157 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
+Normal rank
@@ Property / cites work @@
+On the complexity of communication complexity
@@ Property / cites work: On the complexity of communication complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+On the Shannon capacity of a graph
@@ Property / cites work: On the Shannon capacity of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q4407449
@@ Property / cites work: Q4407449 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication complexity and combinatorial lattice theory
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+Quantum Computer Science
@@ Property / cites work: Quantum Computer Science / rank @@
+Normal rank
@@ Property / cites work @@
+Q2706552
@@ Property / cites work: Q2706552 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the extension complexity of the knapsack polytope
+Normal rank
@@ Property / cites work @@
+On the distributional complexity of disjointness
@@ Property / cites work: On the distributional complexity of disjointness / rank @@
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+Q3549626
@@ Property / cites work: Q3549626 / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Q3392273
@@ Property / cites work: Q3392273 / rank @@
+Normal rank
@@ Property / cites work @@
+Reformulation and Decomposition of Integer Programs
+Normal rank
@@ Property / cites work @@
+Quantum communication and complexity.
@@ Property / cites work: Quantum communication and complexity. / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Quantum Query and Communication Complexities
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank
@@ Property / cites work @@
+Lectures on Polytopes
@@ Property / cites work: Lectures on Polytopes / rank @@
+Normal rank