Extension complexity of the correlation polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh, Marco Macchia, Johanna Seif

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

We prove that for every n-vertex graph G, the extension complexity of the correlation polytope of G is 2O(tw(G)+logn), where tw(G) is the treewidth of G. Our main result is that this bound is tight for graphs contained in minor-closed classes.

Original languageEnglish
Pages (from-to)47-51
Number of pages5
JournalOperations Research Letters
Volume47
Issue number1
DOIs
Publication statusPublished - 1 Jan 2019
Externally publishedYes

Keywords

  • Correlation polytope
  • Extension complexity
  • Graph minors
  • Machine learning
  • Treewidth

Cite this