Monique Laurent (CWI / Tilburg U)
Friday, July 13, 2018 - 14:15
Harnack-Haus (Goethe-Saal)
Ihnestr. 16-20, 14195 Berlin
BMS Friday colloquium
Berlin Mathematical School
Finding a ranking of a set of objects based on information on their pairwise similarities is a fundamental problem in data analysis. A widely used approach is seriation, which aims to order the objects in such a way that similar objects are close to each other. Seriation roots lie in early works by the archeologists Flinders Petrie (1899) and Robinson (1951), who used it for chronological sequencing of Egyptian tombs based on historical remains (like pottery wares) found in them. Recent applications of seriation include genome sequencing and ranking in recommender systems.

In her talk, Laurent will discuss, next to a classical spectral approach, new combinatorial algorithms for this problem of reordering similarity data matrices. She will highlight links to some graph properties that can be exploited to design efficient ranking algorithms. In a nutshell, these algorithms rely on a natural extension to the setting of matrices (weighted graphs) of basic graph search primitives like breadth-first search. No specific preknowledge is required.

Monique Laurent is a French mathematician, who specializes in discrete and polynomial optimization. She has been a researcher at Centrum Wiskunde & Informatica in Amsterdam since 1997 and a member of the CWI Management Team since 2016. Laurent got her PhD at Paris Diderot U in 1986, held research positions at CNET (France) and at U Bonn as a Humboldt Fellow, and was researcher at CNRS (Paris) from 1988 to 1997. She gave an invited lecture at the ICM in 2014 and was elected as a SIAM Fellow in 2017. She is also a part-time full professor at Tilburg University.
submitted by Tanja Fagel (, +493031478653)