Philippe Flajolet, the father of

Analytic Combinatorics


Philippe Flajolet, mathematician and computer scientist extraordinaire, suddenly passed away on March 22, 2011, at the prime of his career. He is celebrated for opening new lines of research in analysis of algorithms, developing powerful new methods, and solving difficult open problems. His research contributions will have impact for generations, and his approach to research, based on curiosity, a discriminating taste, broad knowledge and interest, intellectual integrity, and a genuine sense of camaraderie, will serve as an inspiration to those who knew him for years to come.

The common theme of Flajolet's extensive and far-reaching body of work is the scientific approach to the study of algorithms, including the development of requisite mathematical and computational tools. During his forty years of research, he contributed nearly 200 publications, with an important proportion of fundamental contributions and representing uncommon breadth and depth. He is best known for fundamental advances in mathematical methods for the analysis of algorithms, and his research also opened new avenues in various domains of applied computer science, including streaming algorithms, communication protocols, database access methods, data mining, symbolic manipulation, text-processing algorithms, and random generation. He exulted in sharing his passion: his papers had more than than a hundred different co-authors and he was a regular presence at scientific meetings all over the world.

His research laid the foundation of a subfield of mathematics, now known as analytic combinatorics. His lifework *Analytic Combinatorics* (Cambridge University Press, 2009, co-authored with R. Sedgewick) is a prodigious achievement that now defines the field and is already recognized as an authoritative reference.

Analytic combinatorics is a modern basis for the quantitative study of combinatorial structures (such as words,  trees,  mappings, and graphs), with applications to probabilistic study of algorithms that are based on these structures. It also strongly influences other scientific domains, such as statistical physics, computational biology, and information theory. With deep historic roots in classical analysis, the basis of the field lies in the work of Knuth, who put the study of algorithms on a firm scientific basis starting in the late 1960s with his classic series of books. Flajolet’s work takes the field forward by introducing original approaches in combinatorics based on two types of methods: symbolic and analytic. The symbolic side is based on the automation of decision procedures in combinatorial enumeration to derive characterizations of generating functions. The analytic side treats those functions as functions in the complex plane and leads to precise characterization of limit distributions. In the last few years, Flajolet was further extending and generalizing this theory into a meeting point between information theory, probability theory and dynamical systems.

Philippe Flajolet was born in Lyon on December 1, 1948. He graduated from Ecole Polytechnique in Paris in 1970, and was immediately recruited as a junior researcher at the Institut National de Recherche en Informatique et en Automatique (INRIA), where he spent his career. Attracted by linguistics and logic, he worked on formal languages and computability with Maurice Nivat, obtaining a PhD from the University of Paris 7 in 1973. Then, following Jean Vuillemin in the footsteps of Don Knuth, he turned to the emerging field of analysis of algorithms and got a Doctorate in Sciences, both in mathematics and computer science, from the University of Paris at Orsay in 1979. At INRIA, he created and led the ALGO research group, which attracted visiting researchers from all over the world.

He held numerous visiting positions, at Waterloo, Stanford, Princeton, Wien, Barcelona, IBM and the 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.

A brilliant, insightful "honnête homme" with broad scientific interests, Philippe pursued new discoveries in computer science and mathematics and shared them with students and colleagues for over 40 years with enthusiasm, joy, generosity, and warmth. In France, he was the major reference at the interface between mathematics and computer science and founded the "Alea" meetings that bring together combinatorialists, probabilists and physicists to share problems and methods involving discrete randomness. More broadly, he was the leading figure in the development of the international "AofA" community that is devoted to research on probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms.  The colleagues and students who are devoted to carrying on his work form the core of his primary legacy.

Bruno Salvy, INRIA

Bob Sedgewick, Princeton

Michele Soria, Paris 6

Wojciech Szpankowski, Purdue

Brigitte Vallee, Univ. Caen