The extension complexity of polytopes with bounded integral slack matrices

DOI10.1007/978-3-031-59835-7_9MaRDI QIDQ7030569zbMATH OpenFDO

Authors Sally Dong, Thomas Rothvoß

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_9

zbMATH Keywords

extension complexitypolytopeslack matrix

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• Communication Complexity
• Communication is bounded by root of rank
• Complexity measures of sign matrices
• Exponential lower bounds for polytopes in combinatorial optimization
• Extended formulations in combinatorial optimization
• On rank vs. communication complexity
• Positive semidefinite rank
• The matching polytope has exponential extension complexity

Cited in

(1)

• Stability for binary scalar products

This page was built for publication: The extension complexity of polytopes with bounded integral slack matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030569)