November 19, 2018
by the Public Awareness Office, American Mathematical Society,
2019 Steele Prize for Mathematical Exposition Goes to Philippe Flajolet and Robert Sedgewick
photo by David Kelly Crow
The 2019 Steele Prize for Mathematical Exposition is awarded to Philippe Flajolet (posthumously) of INRIA (Institut National de Recherche en Informatique et en Automatique) and Robert Sedgewick of Princeton University for their book Analytic Combinatorics, an authoritative and highly accessible compendium of its subject, which demonstrates the deep interface between combinatorial mathematics and classical analysis.
It is a rare work, one that defines the relatively young subject in its title, mixing equal parts of complex analysis and combinatorial structure. The authors have combined their extraordinary analytical and expository skills to organize the entire subject into a well-developed and fascinating story. Its publication in 2009 was a major event, and as a result, analytic combinatorics is now a thriving subdiscipline of combinatorial and stochastic mathematics, as well as a key component of the analysis of algorithms.
Quoting Robin Pemantle’s 2010 review of Analytic Combinatorics, published in SIAM Review, “This is one of those books that marks the emergence of a subfield.” The book magically summarizes a vast amount of information. It identifies and expounds key techniques that have never been explained so well before, while consistently paying proper attention to the historical contest. It features world-class graphics and typesetting, and a definitive biography. The book is largely self-contained and a pleasure to read---any mathematician can use it as the basis for teaching a course on analytic combinatorics as an undergraduate elective in mathematics.
Biographical sketch of Philippe Flajolet (1948-2011)
Philippe Flajolet was an extraordinary French mathematician and computer scientist. He graduated from École Polytechnique in Paris in 1970, obtained a PhD from Université Paris 7 with Maurice Nivat in 1973 and got a Doctorate in Sciences from the University of Paris at Orsay in 1979. He spent his career at the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France where he eventually led the ALGO research group, which produced numerous outstanding young scientists and attracted visiting researchers from all over the world.
He held numerous visiting positions, at Waterloo, Stanford, Princeton, Wien, Barcelona, IBM and Bell Laboratories. He received several prizes, including the Grand Science Prize of UAP (1986), the Computer Science Prize of the French Academy of Sciences (1994), and the Silver Medal of CNRS (2004). He was elected a Corresponding Member (Junior Fellow) of the French Academy of Sciences in 1994, a Member of the Academia Europaea in 1995, and a Member (Fellow) of the French Academy of Sciences in 2003. He was made a knight of the Légion d'Honneur in 2010.
Flajolet’s extensive and far-reaching research in mathematics and computer science spanned formal languages, computer algebra, combinatorics, number theory, and analysis, all oriented towards the study of algorithms and discrete structures. During his forty years of research, he contributed nearly 200 publications. An important proportion of these are foundational contributions, or represent uncommon breadth and depth. Highlights range from pioneering work in computer algebra in the 1980s, to theorems in asymptotic analysis in the 1990s that inspired decades of later research, to a probabilistic algorithm that is widely used in modern cloud computing. Much of his research laid the foundation for the development, with Sedgewick, of the subfield of mathematics that is now known as analytic combinatorics, a calculus for the study of discrete structures.
These research contributions will have impact for generations. Flajolet's approach to research, based on endless curiosity, discriminating taste, deep knowledge, relentless computational experimentation, broad interest, intellectual integrity, and genuine camaraderie, will serve as an inspiration to those who knew him for years to come.
Biographical sketch of Robert Sedgewick
Robert Sedgewick is the William O. Baker Professor in the Department of Computer Science at Princeton University. Born in 1946 in Willimantic, Connecticut, he graduated from Brown University in 1968 and did his doctoral work with Donald E. Knuth at Stanford University, receiving his PhD in 1975. After ten years on the faculty at Brown, he left to be the founding chair of Princeton's Department of Computer Science in 1985. He served for 26 years as a member of the board of directors of Adobe Systems and has held visiting research positions at Xerox PARC, IDA, INRIA, and Bell Laboratories.
Sedgewick is the author of twenty books. He is best known for Algorithms, which has been a best-selling textbook since the early 1980s and is now in its fourth edition. His other current textbooks include An Introduction to the Analysis of Algorithms and Analytic Combinatorics (with Philippe Flajolet) and Computer Science: An Interdisciplinary Approach (with Kevin Wayne).
Beyond his work with Flajolet on analytic combinatorics, Sedgewick's research is characterized by a scientific approach to the study of algorithms and data structures, where careful implementations and appropriate mathematical models are validated by experimentation and then used to understand performance and develop improved versions. Many of his research results are expressed in his Algorithms books, and his implementations routinely serve as reference and are featured throughout our global computational infrastructure.
In recent years, Sedgewick has been a pioneer in developing modern approaches to disseminating knowledge, from introductory to graduate level. He has developed six massive open online courses (MOOCs) and published extensive online content on analysis of algorithms and analytic combinatorics and, with Kevin Wayne, algorithms and computer science. These materials have made it possible and convenient for millions of people around the world to teach and learn these subjects, particularly in regions where access to higher education is difficult.
-Response of Robert Sedgewick
"This award is thrilling and humbling for me, but also bittersweet, because Philippe is not here to share it. But all of us who were there vividly remember his excitement at our event in Paris on the occasion of his 60th birthday when we presented him with the first printed copy of Analytic Combinatorics. I keep the look on his face at that moment fresh in my mind, and know that the same look would grace us now.
Philippe and I (and many others) were students of the the work of Don Knuth in the 1970s, and inspired by the idea that it was possible to develop precise information about the performance of computer programs through classical analysis. When we first began working together in 1980, our goal was just to organize models and methods that we could use to teach our students what they needed to know. As we traveled between Paris and Princeton, producing conference papers, journal articles, and INRIA research reports, we began to understand that something more general was at work, and Analytic Combinatorics began to emerge. It is particularly gratifying to see citations of the book by researchers in physics, chemistry, genomics, and many other fields of science, not just mathematicians and computer scientists.
Analyzing algorithms is challenging---at the outset, known results were often either excessively detailed or rough, questionably useful approximations. Thus, what fun it was to consider the idea that maybe (despite the formidable barrier of the Halting Problem) one could develop a black box that could take a program as input and produce as output an asymptotic estimate of its running time. How challenging it was to develop a rigorous calculus that takes us from simple formal descriptions of combinatorial objects through properties of generating functions in the complex plane to precise information about the objects. How exciting it was to build on this work to develop theorems of sweeping generality that encompass whole families of combinatorial classes. As Philippe said, developing new theorems like these "constitutes the very essence of analytic combinatorics.” With a vibrant community of researchers working on developing and applying such theorems, I suspect and hope that the story of analytic combinatorics is just in its infancy.
I am particularly heartened by the statement in the citation that any mathematician could use our book to teach an undergraduate course on the subject. Having the broadest possible reach was indeed our hope when, with the support of our editor, we provided free access to the book on the web. For the past several years, I have been working hard to apply 21st-century tools to develop a unique resource for teaching this material. Anyone can now teach and learn Analytic Combinatorics using the studio-produced lecture videos, new problems with solutions, and other online content. Philippe, who always embraced technology, would be particularly pleased with the idea that it now makes analytic combinatorics accessible to large numbers of people around the world."
About the Steele Prize for Mathematical Exposition
The Leroy P. Steele Prize for Mathematical Exposition is awarded annually for a book, substantial survey, or expository research paper. The 2019 prize will be awarded Thursday, January 17 during the Joint Prize Session at the 2019 Joint Mathematics Meetings in Baltimore which includes the American Mathematical Society (AMS) and the Mathematical Association of America (MAA).
Find out more about the Steele Prize for Mathematical Exposition and see previous recipients.