Brown CS News

Held annually, the Franco Preparata Distinguished Lecture Series brings prominent scientists to Brown University’s Department of Computer Science (Brown CS) in honor of An Wang Professor Emeritus of Computer Science Franco Preparata, an esteemed faculty member who retired a decade ago. The series addresses timely research in theoretical computer science, an area of particular interest to Franco. This year’s lecture, held on October 23, 2025, was delivered by Claire Mathieu, a former Brown CS faculty member who currently serves as research director at the Centre National de la Recherche Scientifique (CNRS) in Computer Science at Université Paris-Cité (France).

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 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 Association for Computing Machinery (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 has served on the editorial boards of six premier journals in theoretical computer science.

Prior to working at CNRS and Brown CS, Claire held visiting appointments at various institutions that included Rutgers University, University of California, Berkeley, Princeton University, Cornell University, and Microsoft Research. Her research focuses on approximation algorithms for combinatorial optimization problems. In 2017-2019, she served as advisor to the French government on the overhaul of the French college admissions system. She is a member of the French Academy of Sciences and a Fellow of the EATCS.

In his opening remarks, Franco expressed his gratitude to Brown CS for establishing a lecture series centered on an area to which he’s devoted much of his lifetime, theoretical computer science. Claire, he added, was “the most brilliant” of a group of young graduate students that he met during his time at the Ecole Normale Supérieure, someone that the Department “felt compelled” to hire, and who served with “wisdom, grace, and science”.

Currently, he explained, she plays a very important role in French computer science as part of the National Research Council. 

“I’m very glad,” he concluded, “that this occasion brings her back here to these shores. Tu es toujours la bienvenue chez nous, Claire!”

“It’s a great pleasure for me to be here today,” Claire said as she stepped to the podium, explaining that she once taught CS 157 (now CSCI 1570) in the very same room.

“I have only good memories from Brown,” Mathieu noted, explaining that it was the place where she truly achieved an understanding of what her profession was about. “I hope Brown continues this way forever.”

Claire situated her talk by explaining that in 2018, the French government decided to overhaul the organization of college admissions, the process through which twelfth-grade students enter the world of higher education. For two years, she spent one day per week at the Ministry of Higher Education and Research to help with the foundational aspects of the reform they were implementing.

“I want to tell you about the theory,” she said, “and the practice.” 

In short, students are looking for schools, schools are looking for students (more than 800,000 applicants and over 10,000 degree programs in 2018) – how are they matched? Simply letting the market rule, Claire said, produces chaos, so some order is needed. 

“In France,” she said to laughter, “we’re good at putting in some regulation.”

The method rests on the well-known Gale-Shapley algorithm, which finds a “stable” assignment, thus preventing the creation of a “behind-the-scenes market” in which users achieve better results by working outside the system. When Claire began her work on the admissions process, the Ministry had just decided that the new method being designed would handle uncertainties with time. Therefore, the system would iterate daily, ending on the day when classes begin and all tentative acceptances become final. This raised the question of analyzing the running time, for which they contributed some modelling and simulations.  

However, three algorithmic questions remained, centered on the need to address quotas of low-income students, quotas of local students, and the coupling of school assignments with the assignment of dorm beds. In response to an ambiguous law, Claire and her collaborator, Hugo Gimbert, navigated a landscape of political choice that provided no obvious solution by offering work that first addressed the interaction between the two types of quotas, then the challenge posed by students who would only accept an offer if the college also agreed to provide housing.

In the end, Claire said simply, the two collaborators created an algorithm that provided a feasible solution, later formally proved to be correct. The project, she explained, offered her a reminder of what theory of computing brings to the table: algorithmic techniques and representations, rigorous perspective, and proofs.

“And what did I learn from this?” Claire asked. “Many, many things, but if I were going to say one thing from this, it’s the importance of simplicity. The advantage of simplicity cannot be overrated.”

A recording is available (Brown login required) here.

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