Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

No abstract is available for this paper.

• Publication year

  2011

• Venue

  Symposium on the Theory of Computing

• Publication date

  2011-11-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2213977.2213988
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Communication Complexity

  2016cited by this paper
• Approximation Limits of Linear Programs (Beyond Hierarchies)

  2012cited by this paper
• Correlation/Communication complexity of generating bipartite states

  2012cited by this paper
• Quantum Computation and Quantum Information

  2012cited by this paper
• Symmetry Matters for Sizes of Extended Formulations

  2012cited by this paper
• Extended Formulations in Combinatorial Optimization

  2011cited by this paper
• Some 0/1 polytopes need exponential size extended formulations

  2011influential reference
• Extended formulations, nonnegative factorizations, and randomized communication protocols

  2011cited by this paper
• Combinatorial bounds on nonnegative rank and extended formulations

  2011cited by this paper
• Lifts of Convex Sets and Cone Factorizations

  2011cited by this paper
• Extended formulations in combinatorial optimization

  2010cited by this paper
• A counterexample to the Alon-Saks-Seymour conjecture and related problems

  2010influential reference
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

  2010cited by this paper
• Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy

  2010cited by this paper
• Quantum strategic game theory

  2010cited by this paper
• Nonlocality and communication complexity

  2010cited by this paper
• Symmetry in Extended Formulations of the Permutahedron

  2009cited by this paper
• On the complexity of communication complexity

  2009cited by this paper
• Quantum Proofs for Classical Theorems

  2009cited by this paper
• Optimal Sherali-Adams Gaps from Pairwise Independence

  2009cited by this paper
• Reformulation and Decomposition of Integer Programs

  2009cited by this paper
• The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection

  2009cited by this paper
• Geometry of cuts and metrics

  2009cited by this paper
• Integrality gaps for Sherali-Adams relaxations

  2009cited by this paper
• Theta Bodies for Polynomial Ideals

  2008cited by this paper
• One-way multiparty communication lower bound for pointer jumping with applications

  2007cited by this paper
• Linear programming relaxations of maxcut

  2007cited by this paper
• Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

  2007cited by this paper
• Quantum Computer Science: An Introduction

  2007cited by this paper
• Lattice problems in NP ∩ coNP

  2005cited by this paper
• Lattice Problems in NP cap coNP

  2004cited by this paper
• Nondeterministic Quantum Query and Communication Complexities

  2003cited by this paper
• Lower bounds for local search by quantum arguments

  2003cited by this paper
• Rank bounds and integrality gaps for cutting planes procedures

  2003cited by this paper
• Semidefinite Programs and Combinatorial Optimization

  2003cited by this paper
• Recent advances in algorithms and combinatorics

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

  2002cited by this paper
• Proving integrality gaps without knowing the linear program

  2002cited by this paper
• Quantum communication and complexity

  2002cited by this paper
• Introduction to the Theory of Computation

  1996cited by this paper
• Lectures on Polytopes

  1994cited by this paper
• Convex analysis and minimization algorithms

  1993cited by this paper
• Communication Complexity and Combinatorial Lattice Theory

  1993cited by this paper
• A lift-and-project cutting plane algorithm for mixed 0–1 programs

  1993cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper
• On the Distributional Complexity of Disjointness

  1990influential reference
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• The cut polytope and the Boolean quadric polytope

  1990cited by this paper
• Disjunctive programming and a hierarchy of relaxations for discrete optimization problems

  1985cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• Polynomial algorithms in linear programming

  1980cited by this paper
• On the Shannon capacity of a graph

  1979cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• The synthesis of two-terminal switching circuits

  1949cited by this paper

• Hard submatrices for non-negative rank and communication complexity

  2025cites this paper
• On the nonnegative ranks of matrices in Puiseux series fields

  2025cites this paper
• Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization

  2024influential citation
• Sudden death of quantum advantage in correlation generations.

  2024cites this paper
• Matroid Products via Submodular Coupling

  2024cites this paper
• The sudden death of quantum advantage in correlation generations

  2024cites this paper
• Uniqueness of size-2 positive semidefinite matrix factorizations

  2024cites this paper
• A Topological Version of Schaefer's Dichotomy Theorem

  2023cites this paper
• The Generations of Classical Correlations via Quantum Schemes

  2023cites this paper
• In Honour of Ted Swart

  2023cites this paper
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations

  2023cites this paper
• Semidefinite Approximations for Bicliques and Bi-Independent Pairs

  2023cites this paper
• Time Lower Bounds for the Metropolis Process and Simulated Annealing

  2023cites this paper
• Further ∃R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exists {\mathbb {R}}$$\end{document}-Complete Problems with

  2023cites this paper
• Simple information-processing tasks with unbounded quantum advantage

  2023cites this paper
• Convexification techniques for fractional programs

  2023cites this paper
• The Exact Bipartite Matching Polytope Has Exponential Extension Complexity

  2022cites this paper
• Self-dual polyhedral cones and their slack matrices

  2022cites this paper
• Restricted Hidden Cardinality Constraints in Causal Models

  2021cites this paper
• Lifts for Voronoi Cells of Lattices

  2021cites this paper
• Noncommutative Polynomial Optimization

  2021cites this paper
• Shadows of newton polytopes

  2021cites this paper
• Factoring a band matrix over a semiring

  2020cites this paper
• On the complexity of computing a random Boolean function over the reals

  2020cites this paper
• On $\epsilon$-sensitive monotone computations

  2020cites this paper
• Quantum and Classical Hybrid Generations for Classical Correlations

  2020cites this paper
• Positive Semidefinite Matrix Factorization Based on Truncated Wirtinger Flow

  2020cites this paper
• On ε-sensitive monotone computations.

  2020cites this paper
• Positive Semidefinite Matrix Factorization: A Link to Phase Retrieval And A Block Gradient Algorithm

  2020cites this paper
• Extension Complexity via Lifting LP Hierarchy Lower Bounds

  2020cites this paper
• Polynomial size IP formulations of knapsack may require exponentially large coefficients

  2020cites this paper
• Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization

  2020cites this paper
• Approximate tensor decompositions: Disappearance of many separations

  2020cites this paper
• Regular matroids have polynomial extension complexity

  2019cites this paper
• Separability for mixed states with operator Schmidt rank two

  2019cites this paper
• A Universality Theorem for Nested Polytopes

  2019cites this paper
• Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices

  2019cites this paper
• Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

  2019cites this paper
• On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims

  2019cites this paper
• Extended Formulation Lower Bounds for Refuting Random CSPs

  2019cites this paper
• SPECTRAHEDRAL LIFTS OF CONVEX SETS

  2018cites this paper
• SPECTRAHEDRAL LIFTS OF CONVEX SETS

  2018cites this paper
• Limits of Treewidth-based tractability in Optimization

  2018cites this paper
• New limits of treewidth-based tractability in optimization

  2018cites this paper
• Strong reductions for extended formulations

  2018cites this paper
• Fe b 20 16 Computing approximate PSD factorizations

  2018cites this paper
• Extended formulations from communication protocols in output-efficient time

  2018cites this paper
• Decision diagrams for optimization

  2018cites this paper
• Extended Formulation Lower Bounds for Combinatorial Optimization

  2018cites this paper
• Size-degree trade-offs for sums-of-squares and positivstellensatz proofs

  2018cites this paper
• Extended Formulations for Radial Cones

  2018cites this paper
• Disjunctive Programming and Extended Formulations

  2018cites this paper
• The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes

  2018cites this paper
• On some problems related to 2-level polytopes

  2018cites this paper
• On the linear extension complexity of stable set polytopes for perfect graphs

  2017cites this paper
• Bernoulli Correlations and Cut Polytopes

  2017cites this paper
• A Heuristic for a Mixed Integer Program using the Characteristic Equation Approach

  2017cites this paper
• The Matching Polytope has Exponential Extension Complexity

  2017influential citation
• A Variational Principle for Ground Spaces

  2017cites this paper
• The Slack Realization Space of a Polytope

  2017cites this paper
• The Rectangle Covering Number of Random Boolean Matrices

  2017cites this paper
• On tropical and nonnegative factorization ranks of band matrices

  2017cites this paper
• Algorithms for positive semidefinite factorization

  2017cites this paper
• A separation between tropical matrix ranks

  2017cites this paper
• Decomposition techniques applied to the Clique-Stable set Separation problem

  2017influential citation
• Transport in Unsteady Flows: from Deterministic Structures to Stochastic Models and Back Again (17w5048)

  2017cites this paper
• The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions

  2016cites this paper
• Rank functions of tropical matrices

  2016cites this paper
• Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

  2016cites this paper
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes

  2016cites this paper
• Recommender systems inspired by the structure of quantum theory

  2016cites this paper
• Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)

  2016cites this paper
• The Complexity of Positive Semidefinite Matrix Factorization

  2016cites this paper
• On "Exponential Lower Bounds for Polytopes in Combinatorial Optimization" by Fiorini et al. (2015): A Refutation For Models With Disjoint Sets of Descriptive Variables

  2016cites this paper
• A Small-Order-Polynomial-Sized Linear Program for Solving the Traveling Salesman Problem

  2016influential citation
• Nonnegative rank depends on the field II

  2016cites this paper
• Strong Relaxations for Discrete Optimization Problems 15 / 04 / 16 Lecture : Yannakakis ’ theorem and the correlation polytope

  2016cites this paper
• Strong Relaxations for Discrete Optimization Problems 29 / 04 / 16 Lecture : Extension complexity of stable set and matching polytopes

  2016cites this paper
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

  2016cites this paper
• The Parity Hamiltonian Cycle Problem in Directed Graphs

  2016cites this paper
• The Complexity of Extended Formulations

  2016influential citation
• Deciding Graph non-Hamiltonicity via a Closure Algorithm

  2016cites this paper
• Global Completability with Applications to Self-Consistent Quantum Tomography

  2016cites this paper
• Information-theoretic approximations of the nonnegative rank

  2016cites this paper
• Computing approximate PSD factorizations

  2016cites this paper
• Cutting planes from extended LP formulations

  2016cites this paper
• Maximum semidefinite and linear extension complexity of families of polytopes

  2016cites this paper
• A short proof that NMF is NP-hard

  2016cites this paper
• Extended Formulations for Online Action Selection on Big Action Sets

  2016cites this paper
• A universality theorem for nonnegative matrix factorizations

  2016cites this paper
• Extended Formulations for Independence Polytopes of Regular Matroids

  2015cites this paper
• On the Power of Lasserre SDP Hierarchy

  2015cites this paper
• No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e

  2015cites this paper
• Quantum and classical coin-flipping protocols based on bit-commitment and their point games

  2015cites this paper
• Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

  2015cites this paper
• Mixed Integer Linear Programming Formulation Techniques

  2015cites this paper
• Strong reductions for extended formulations

  2015cites this paper
• Monotone Projection Lower Bounds from Extended Formulation Lower Bounds

  2015cites this paper
• Branch-and-Cut for Nonlinear Power Systems Problems

  2015cites this paper
• Tight extended formulations for independent set ∗

  2015cites this paper