Data Driven Algorithm Design

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.