Samuel Fiorini
Université Libre de Bruxelles
Département de Mathématique
CP 216 (Service de Géométrie, Combinatoire et Théorie des Groupes)
Boulevard du Triomphe
B-1050 Bruxelles
Belgium
tel: +32 (0) 2 650 58 88, fax: +32 (0) 2 650 58 67
sfiorini "at" ulb "dot" ac "dot" be
For an up-to-date CV, see here.
Check out my new paper with Serge Massar (ULB), Sebastian Pokutta (Erlangen U.), Hans Raj Tiwary (ULB) and Ronald de Wolf (CWI):
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.