Philippe Flajolet

Quick Info

1 December 1948
Lyon, France
22 March 2011
Paris, France

Philippe Flajolet was a French mathematician and computer scientist who worked on the analysis of algorithms.


Philippe Flajolet's grandfather, also named Philippe Flajolet (1885-1948), was an astronomer who worked at the Observatory at Lyon. Philippe, the subject of this biography, was brought up in Lyon where he entered the Lycée Ampère in 1958. He spent seven years at the Lycée, retaining fond memories of these years, where he was taught mathematics by A Giberne and Georges Thovert. Graduating with his Baccalauréat in 1966, he entered the École Polytechnique in 1968 where he studied for three years. In 1971, after graduating from the École Polytechnique, he joined the Institut National de Recherche en Informatique et en Automatique where he was appointed as a junior researcher. He continued to work at the Institut for the rest of his career.

While at the École Polytechnique, Flajolet had become interested in the theory of computing and the theory of languages by reading the works of Louis Comtet, Leonard Euler, Donald Knuth and Srinivasa Ramanujan. It was Maurice Paul Nivat who recruited Flajolet to work at the Institut National de Recherche en Informatique et en Automatique but, in addition to him, Jean Vuillemin and Marcel-Paul Schützenberger, who had been appointed as Professor in the Faculty of Sciences at the University of Paris VII in 1970, were major influences on the young researcher. He worked closely with a colleague, Jean-Marc Steyaert, and they collaborated in writing papers such as: Complexité des problèmes de décision relatifs aux algorithmes de tri (1972); A class of non-recursive sorting algorithms (1973); and Decision problems for multihead finite automata (1973). Flajolet and Steyaert presented Une formalisation de la notion d'algorithme de tri non récurrent as a joint work to the Université de Paris VII for their Ph.D.'s in 1973. Flajolet presented his Habilitation thesis Analyse d'algorithmes de manipulation d'arbres et de chiers to Université de Paris XI, Orsay in 1979 and was awarded the degree of Doctorat ès Sciences both in mathematics and computer science.

In 1976, together with Jean Vuillemin, he founded the ALGO group within the Institut National de Recherche en Informatique et en Automatique which had as its main task the analysis of algorithms. We have seen that his Doctorat ès Sciences thesis of 1979 was on this topic, but many of his papers looked at various aspects of this topic. For example (with Jean-Marc Steyaert) On the analysis of tree-matching algorithms (1980), (with Guy Fayolle, Philippe Flajolet, Micha Hofri, and Philippe Jacquet) Analysis of a stack algorithm for random multiple-access communication (1983), Methods in the analysis of algorithms (1983), Mathematical methods in the analysis of algorithms and data structures (1988), and the book, written with Robert Sedgewick, An Introduction to the Analysis of Algorithms (1996). Flajolet became head of the ALGO group in 1981.

The authors of [5], [6], [7], [8], [9] write:-
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 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 a hundred different co-authors and he was a regular presence at scientific meetings all over the world.
One of the important new areas that he developed was 'analytic combinatorics'. Let us give his own description of this topic, as he described it in the Preface to the remarkable book, written jointly with Robert Sedgewick, Analytic Combinatorics (2009). Let us note that this book in many ways can be seen as summing up his life-long work:-
'Analytic combinatorics' aims at predicting precisely the properties of large structured combinatorial configurations, through an approach based extensively on analytic methods. Generating functions are the central objects of study of the theory. 'Analytic combinatorics' starts from an exact enumerative description of combinatorial structures by means of generating functions: these make their first appearance as purely formal algebraic objects. Next, generating functions are interpreted as analytic objects, that is, as mappings of the complex plane into itself. Singularities determine a function's coefficients in asymptotic form and lead to precise estimates for counting sequences. This chain of reasoning applies to a large number of problems of discrete mathematics relative to words, compositions, partitions, trees, permutations, graphs, mappings, planar configurations, and so on. A suitable adaptation of the methods also opens the way to the quantitative analysis of characteristic parameters of large random structures, via a perturbational approach. The approach to quantitative problems of discrete mathematics provided by analytic combinatorics can be viewed as an operational calculus for combinatorics organized around three components.

'Symbolic methods' develops systematic relations between some of the major constructions of discrete mathematics and operations on generating functions that exactly encode counting sequences.

'Complex asymptotics' elaborates a collection of methods by which one can extract asymptotic counting information from generating functions, once these are viewed as analytic transformations of the complex domain. Singularities then appear to be a key determinant of asymptotic behaviour.

'Random structures' concerns itself with probabilistic properties of large random structures. Which properties hold with high probability? Which laws govern randomness in large objects? In the context of analytic combinatorics, these questions are treated by a deformation (adding auxiliary variables) and a perturbation (examining the effect of small variations of such auxiliary variables) of the standard enumerative theory.
Flajolet received many honours throughout his career. He was awarded the Grand Prix Scientifique by the Union des assurances de Paris in 1986, the Michel Monpetit prize from the French Academy of Sciences in 1994, and the Silver Medal from the French National Centre for Scientific Research in 2004. He was elected as a corresponding member of the Academy of Sciences in 1993 and a full member on 18 November 2003. He was elected as a member of the Academia Europaea in 1995, and then he was elected to the European Academy of Sciences. He was made a knight of the Légion d'Honneur in July 2010. In 1998, to celebrate his 50th birthday, the journal Algorithmica issued a special part. This part contains Helmut Prodinger and Wojciech Szpankowski's survey article Philippe Flajolet's research in analysis of algorithms and combinatorics. Ten years later, his 60th birthday was marked with a Colloquium held in Paris on 1-2 December 2008, with papers presented at this meeting published in the journal Discrete Mathematics and Theoretical Computer Science. A conference, 'Philippe Flajolet and Analytic Combinatorics: Conference in the memory of Philippe Flajolet', was held at Paris-Jussieu, 14-16 December 2011. The conference announcement read:-
This conference will pay homage to the man as well as the multi-faceted mathematician and computer-scientist. It will also help more people understand his rich and varied work, through talks aimed at a large audience. ... Most of the talks will form a basis for an introduction to the corresponding chapter in Philippe Flajolet's collected works, to be edited soon.
Indeed, his Complete Works are being prepared for publication by Cambridge University Press and the seven-volume work is expected to appear in 2013.

Finally, let us give the vivid picture of Flajolet as given by Luc Devroye [3]:-
The image that is etched in my mind is that of Philippe Flajolet happily purring while listening to a great exposition by one of his students or colleagues. At the first opportunity, he would shout something funny in the direction of the speaker to show his appreciation. He was the community's cheerleader. The inside of his car has never been cleaned, his hair camouflaged a biological experiment, his shirts were always untucked, and yet, wherever he went, he was inevitably surrounded by friends and followers, admired for his brilliance and wit, and revered for his guidance and generosity. ... he was a master of mathematical illustration. He liked to show that craft off in his passionate talks, which grew more intense with every tick of the clock, to end up in overtime. On one occasion, I saw the last button of his shirt pop off just before the final slide. [He started wearing Indian-style shirts above his belt in the last decade of his life to avoid such events.] One of his other passions was listening. His seminar series in Versailles was legendary. It was an honour to be invited. And Philippe listened, purred, teased, shouted, applauded, and acted up - anything short of throwing a paper airplane at the speaker with a heart drawn on its wings. He was the glue that kept the community together.

References (show)

  1. A Bostan, N Broutin, F Chyzak, V Collette, P Dumas and B Salvy, Philippe Flajolet chez ALGO, Gaz. Math. No. 129 (2011), 115-116.
  2. B Chauvin, B Salvy, M Soria and B Vallée, Philippe Flajolet, le fondateur de la combinatoire analytique, Gaz. Math. No. 129 (2011), 113-114.
  3. L Devroye, My friend, Gaz. Math. No. 129 (2011), 116-117.
  4. Philippe Flajolet, 1 December 1948-22 March 2011.
  5. B Salvy, B Sedgewick, M Soria, W Szpankowski and B Vallée, Philippe Flajolet, the father of analytic combinatorics, ACM Trans. Algorithms 7 (4) (2011), Art. 40.
  6. B Salvy, B Sedgewick, M Soria, W Szpankowski and B Vallée, Philippe Flajolet, the father of analytic combinatorics, Assoc. Theor. Comput. Sci. EATCS No. 104 (2011), 16-18.
  7. B Salvy, B Sedgewick, M Soria, W Szpankowski and B Vallée, Philippe Flajolet, the father of analytic combinatorics, Random Structures Algorithms 39 (1) (2011), iii-iv.
  8. B Salvy, B Sedgewick, M Soria, W Szpankowski and B Vallée, Philippe Flajolet: 1 December 1948-22 March 2011, Combin. Probab. Comput. 20 (5) (2011), 647-649.
  9. B Salvy, B Sedgewick, M Soria, W Szpankowski and B Vallée, Obituary. Philippe Flajolet, J. Symbolic Comput. 46 (9) (2011), 1085-1086.
  10. J-M Steyaert, Avoir eu vingt ans avec Philippe, Gaz. Math. No. 129 (2011), 121-122.
  11. B Vallée, Vingt-cinq ans de compagnonnage scientique avec Philippe Flajolet, Gaz. Math. No. 129 (2011), 118-120.

Additional Resources (show)

Written by J J O'Connor and E F Robertson
Last Update July 2012