Monique Laurent

Centrum Wiskunde & Informatica, and Tilburg University, Netherlands

Monique Laurent obtained her PhD in Mathematics at the University Paris Diderot in 1986. During her PhD studies, she was a visiting researcher at New York University in the period 1984–1986. After two years as a researcher at CNET (Paris), she became a researcher at CNRS in 1988, affiliated first with University Paris Dauphine and from 1992 with École Normale Supérieure. In 1990–1992, she visited the Institute of Discrete Mathematics in Bonn as a Humboldt Fellow. From 1997, she joined CWI as a senior researcher. She was group leader of Networks and Optimization (N&O) between 2005 and 2016, and a member of the CWI Management Team between 2016 and 2021. She has also been affiliated as a part-time full professor at Tilburg University since 2009. She became a SIAM Fellow in 2017, a EUROPT Fellow in 2021, and she received the Khachiyan Prize 2023 from the INFORMS Optimization Society.

Talk Title: Graph elliptopes: combinatorial, geometric and algebraic aspects

Abstract: The set of nxn positive semidefinite matrices with an all-ones diagonal (aka correlation matrices) is a well-studied convex set, known as the elliptope En. It plays an important role within several research areas, including distance geometry, matrix completion problems, combinatorial optimization, and algebraic statistics. For instance, the elliptope En provides the semidefinite relaxation underlying the celebrated 0.878-approximation algorithm of Goemans & Williamson (1995) for the max-cut problem, and its projection E(G) onto the subspace indexed by the edge set of a graph G is at the core of the PSD matrix completion problem. Testing membership in E(G) is a basic instance of semidefinite programming feasibility problem, whose exact complexity status is still unknown. We will discuss some old and new results about graph elliptopes. For some graph classes (chordal, series-parallel, and cycle-completable graphs), the associated graph elliptope E(G) admits a structural characterization involving PSD constraints and related metric polyhedra. Interestingly, this uncovers a tight link with trigonometric parametric representations of certain algebraic varieties. We aim to highlight these combinatorial, geometric and algebraic connections. As a byproduct, while - by construction - every graph elliptope E(G) is a spectrahedral shadow, one can show that E(G) is a spectrahedron (i.e., the feasibility region of an SDP) precisely when the graph G is chordal. Based on joint work with Francesco Mascarin and Simon Telen.

Website: Personal webpage

</div> </div>