In this lecture we discuss how to complete a partially specified matrix to a positive semi-definite matrix. This includes questions like deciding existence and constructing a completion, and determining the smallest possible rank of a completion. We present structural results and algorithms that take the graph of specied entries into account. This combinatorial approach leads to links between various areas: cut and metric polytopes in combinatorial op- timization, correlation matrices and distance matrices in distance geometry, Euclidean graph realizations and Colin de Verdiere type geometric graph invariants.

Monique Laurent is leader of the research group Algorithms, 

Combinatorics

and Optimization at CWI in Amsterdam and professor at

the University of Tilburg. She received her PhD degree in Mathematics 

at the University

Paris Diderot in 1986. Before joining CWI in 1997, she has held 

positions at CNET and at CNRS in Paris.

She was also a Humboldt fellow at the University of Bonn in 1991/92 and 

had visiting positions e.g. at Yale University,

IASI-CNR in Rome, and Tokyo Institute of Technology.

Her research field is combinatorial optimization with a focus on

algorithmic methods using algebraic tools and semidefinite programming.

She has more than 80 publications and co-authored the book `Geometry of 

Cuts and Metrics'.

She is an editor of Mathematics of Operations Research, SIAM Journal on 

Optimization and SIAM Journal on Discrete

Mathematics. She has been involved in national and international EU 

projects and in the organization of

various scientific events, including workshops and seminars on 

Combinatorial Optimization, Semidefinite Programming, and on Algorithms 

for Real Algebraic Geometry in Oberwolfach, and a thematic semester 

program on Optimization at IPAM in Los Angeles.

More information is available at http://www.cwi.nl/~monique