Brown CS News

At 4 PM on Thursday, October 23, Claire Mathieu, Director of Research at the Centre national de la recherche scientifique (CNRS), will deliver the 2025 Franco Preparata Distinguished Lecture ("Stable matchings in theory and practice: the example of French college admissions") in CIT 368. This endowed lecture series honors An Wang Professor Emeritus of Computer Science Franco Preparata, an esteemed member of the Brown CS faculty who retired a decade ago. Held annually, it brings prominent scientists to Brown to address timely research in theoretical computer science, an area of particular interest to Franco.  

Franco’s career spans seven countries and more than a half-century, including twenty-three years with Brown alone. It includes the publication of three books that have been translated into five languages, more than two hundred papers, and seminal contributions to coding theory, computational geometry, design and analysis of algorithms, parallel computing, very-large-scale integration (VLSI) computation, and computational biology. Franco is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), the ACM, and the Japan Society for the Advancement of Science. He’s a recipient of the IEEE Circuits and Systems Society’s Darlington Prize and the “Laurea honoris causa” in Information Engineering from the University of Padova, Italy. He served on the editorial boards of six premier journals in theoretical computer science.

Franco’s early work was in switching and coding theory. He discovered a class of optimal burst-correcting codes (the Berlekamp-Preparata codes) and the first known class of optimum nonlinear codes, known as Preparata codes. He also contributed to a classical model for fault diagnosis in digital systems, commonly referred to as the Preparata-Metze-Chien model. Franco’s interests evolved towards the design and analysis of algorithms. He made pioneering contributions to computational geometry, notably with his optimal convex hull and point-location algorithms and the use of geometric duality. He made seminal contributions to parallel and VLSI computation, notably the cube-connected cycles architecture (with J. Vuillemin) and wire routing methods. His recent work includes computational metrology and computational biology.  Franco was the visionary founder of Brown’s Center for Computational Molecular Biology, which recently celebrated its twentieth anniversary.

Claire's research area concerns the design and analysis of algorithms, particularly the design of approximation algorithms for combinatorial optimization. A former Brown CS faculty member, she was a recipient of the Computer Science Chair at Collège de France, participated in the design of the French Parcoursup platform for college admissions, received the 2019 CNRS Silver Medal, and belongs to the French Academy of Sciences.

"Stable matching methods, based on the deferred acceptance algorithm of Gale and Shapley," she explains, "are used around the world in many applications such as college admissions. The deferred acceptance algorithm has many properties that make it desirable in such a setting; for example, it is stable (no pairwise regret) and runs in polynomial time. It is a theoretically ideal algorithm, simple, elegant and satisfying.

It is the core of the French college admissions system that was reformed in 2018, a reform for which I was a consultant. But several difficulties came up during the process of confronting theory with practice. Do the correlations between individual preferences help or hinder the algorithm? This led to some new 'beyond worst case' results.

Once the system was implemented, the experience on the terrain rose issues with the basic assumptions of the problem itself – the existence of set preferences, in particular. This leads to more open directions."

For more information, click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.