Abstract
This paper introduces a geometric tool to establish lower bounds on the extension complexity of polytopes. By moving from algebraic factorizations to metric geometry—specifically the Hausdorff distance—the authors simplify existing proofs and provide a new upper bound for the linear extension complexity of $0/1$-polytopes.
Introduction: The Extension Complexity Problem
In mathematical optimization, a complex polytope $P$ is often represented as the projection of a simpler set $Q$ in a higher-dimensional space. A linear extension occurs when $Q$ is a higher-dimensional polytope with few facets. Conversely, a semidefinite extension occurs when $Q$ is a spectrahedron, defined by linear matrix inequalities.
The "extension complexity" is the minimum size of such a $Q$. Proving lower bounds—demonstrating that a shape cannot be represented simply—is a significant challenge. While previous methods relied on complex algebraic "slack matrix factorizations," this work proposes a more intuitive geometric approach.
Methodology: Metric Geometry and Hausdorff Distance
The authors utilize metric geometry and the Hausdorff distance to measure the separation between sets in space. The core of their method involves:
- Normalization via John-Löwner Ellipsoids: Every extended formulation is normalized using the unique maximum-volume ellipsoid inscribed in a convex body, placing all representations into a comparable geometric frame.
- Volume Counting and Packing: By treating the space of normalized representations as a high-dimensional metric space, the authors show that if a family of polytopes is "well-separated," there is insufficient "room" in low-complexity representation spaces to accommodate all members.
- General Lower Bound Formula: Theorem 1 links the cardinality of a polytope family and their minimum pairwise distance to a lower bound on extension complexity.
Key Insights
- Geometric Packing: Extension complexity is fundamentally constrained by how shapes are packed in space. Distinct geometric shapes require higher-dimensional representations to be distinguished.
- Simplified Normalization: Using John-Löwner ellipsoids eliminates the need for the complex matrix balancing required in earlier proofs.
- Addressing the 0/1-Polytope Gap: The authors adapted techniques from boolean circuit theory to establish a previously missing non-trivial upper bound for $0/1$-polytopes.
Key Results
- General Lower Bounds: A concrete formula for lower bounds based on family cardinality and spatial separation.
- 0/1-Polytopes: A simpler proof that most $0/1$-polytopes require exponential extension complexity. Additionally, a new upper bound for the linear extension complexity of any $d$-dimensional $0/1$-polytope was established at $O(2^d/d)$, specifically $9 \frac{2^d}{d}$ for $d \ge 4$.
- Improved Polygon Bounds: For $n$-gons on specific integer grids, the lower bound for semidefinite extension complexity was improved to $\Omega(\sqrt[4]{n})$.
Conclusion and Future Work
While these results provide powerful tools for bounding the maximum complexity within a family, they do not yet allow for the calculation of the exact complexity of a specific, individual polytope. The method's power also depends on the "well-separatedness" of the family. Future research remains focused on the exact asymptotics of extension complexity for $n$-gons.
Summary updated