Marco Macchia

activity

20172021

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2021

Slack matrices, $k$ -products, and $2$ -level polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices $S_{1}$ , $S_2…

cs.DM2018

Extension Complexity of the Correlation Polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh +2

We prove that for every $n$ -vertex graph $G$ , the extension complexity of the correlation polytope of $G$ is $2^{O (tw (G) + l o g n)}$ , where $tw (G)$ is the treewid…

Slack matrices, k-products, and 2-level polytopes

Extension Complexity of the Correlation Polytope

Slack matrices, $k$ -products, and $2$ -level polytopes