## Invited Session Tue.3.H 3004

#### Tuesday, 15:15 - 16:45 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Extended formulations in discrete optimization I

**Chair: Samuel Fiorini and Gautier Stauffer**

**Tuesday, 15:15 - 15:40 h, Room: H 3004, Talk 1**

**Sebastian Pokutta**

On linear programming formulations of the TSP polytope

**Coauthors: Ronald de Wolf, Samuel Fiorini, Serge Massar, Hans-Raj Tiwary**

**Abstract:**

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

**Tuesday, 15:45 - 16:10 h, Room: H 3004, Talk 2**

**Thomas Rothvoss**

Some 0/1 polytopes need exponential size extended formulations

**Abstract:**

We prove that there are *0/1* polytopes *P ⊆ ***R**^{n} that do not

admit a compact LP formulation. More precisely we show that for every *n*

there is a set *X ⊆ { 0,1}*^{n}

such that **conv***(X)* must have extension complexity

at least *2*^{n/2·(1-o(1))}. In other words, every polyhedron *Q* that can

be linearly projected on **conv***(X)* must have exponentially many facets.

In fact, the same result also applies if **conv***(X)* is restricted to be a matroid polytope.

The paper is available under:, http://arxiv.org/abs/1105.0036

**Tuesday, 16:15 - 16:40 h, Room: H 3004, Talk 3**

**Roland Grappe**

Extended formulations, non-negative factorizations, and randomized communication protocols

**Coauthors: Yuri Faenza, Samuel Fiorini, Tiwary Hans Raj**

**Abstract:**

We show that the binary logarithm of the non-negative rank of a non-negative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation.

We use this connection to prove new conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.