On the extension complexity of polytopes separating subsets of the Boolean cube

2021/05/25 by Pavel Hrubeš, Hrubeš, Pavel, Navid Talebanfard +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2105.11996

openalex publication_date 2021/05/25 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/31

Abstract

We show that 1. for every A⊆ \0, 1\ⁿ, there exists a polytope P⊆ ℝⁿ with P ∩ \0, 1\ⁿ = A and extension complexity O(2^n/2), 2. there exists an A⊆ \0, 1\ⁿ such that the extension complexity of any P with P∩ \0, 1\ⁿ = A must be at least 2^{(n)/(3)(1-o(1))}. We also remark that the extension complexity of any 0/1-polytope in ℝⁿ is at most O(2ⁿ/n) and pose the problem whether the upper bound can be improved to O(2^cn), for c<1.

Related

• Extension complexity of low-dimensional polytopes
• On the extension complexity of combinatorial polytopes
• Extension complexity of polytopes with few vertices or facets
• The matching polytope has exponential extension complexity
• Maximum Semidefinite and Linear Extension Complexity of Families of\n Polytopes