Pacific Institute for the Mathematical Sciences - PIMS

Bernard Chazelle (born November 5, 1955) is a professor of computer
science at Princeton University. Although he is best known for his
invention of the soft heap data structure and the most asymptotically
efficient known algorithm for finding minimum spanning trees, most of
his work is in computational geometry, where he has found many of the
best-known algorithms, such as linear-time triangulation of a simple
polygon, as well as many useful complexity results, such as lower bound
techniques based on discrepancy theory.
Chazelle originally grew up in Paris, France, where he received his
bachelors degree and masters degree in applied mathematics at the Ecole
des Mines de Paris in 1977. Then, at the age of 22, he came to Yale
University in the United States, where he received his Ph.D. in
computer science. He went on to claim important research positions at
institutions such as Carnegie Mellon, Brown, NEC, Xerox PARC, and the
Paris institutions Ecole Normale Supérieure, Ecole Polytechnique, and
INRIA. As of 2004, he has 191 published articles, 93 of which are
journal articles, and published two books. He has received 18 grants,
12 of which are from the National Science Foundation. He is a fellow of
the ACM, the American Academy of Arts and Sciences, the World
Innovation Foundation, the John Simon Guggenheim Memorial Foundation,
and NEC, as well as a member of the European Academy of Sciences.
Chazelle has also written a few political essays, such as 'Bush's
Desolate Imperium' [1] and 'Anti-Americanism: A Clinical Study' [2],
which draw from his life experience in both France and the United
States.
Chazelle is married to Celia Chazelle, a researcher at the Institute
for Advanced Study. They have one son, Damien, and a daughter, Anna.
Abstract: Motivated by the need to cope with data that is massive,
high-dimensional, noisy, uncertain, unevenly priced, low-entropic, or
all of the above, algorithm design is undergoing profound changes. I
will discuss some of these developments; in particular, sublinear
algorithms, online reconstruction, self-improving algorithms, and
dimension reduction.

PIMS/SFU Computing Science DISTINGUISHED LECTURE SERIES 2006