Skip to content

Philippe Flajolet 1948–2011

March 27, 2011


Some comments on the sad passing of Flajolet

Philippe Flajolet passed away on Tuesday, March 22. He was a larger-than-life theorist, the kind of person who “makes” an institution and becomes one himself.

Today Ken and I want to talk about just a bit of his great contributions to the field of computing. We will all miss him.

It is a very sad time, but somehow it seems right to start by reproducing a cartoon panel which appears as a fresco at the national research laboratory INRIA Rocquencourt where he worked. We hope Philippe would smile and approve.

This depicts him as a character in the Asterix the Gaul series. The “good guys” in this popular humorous adventure comic have names ending in “-ix”: Astérix, Obélix, Panoramix {\dots} As one of the good guys, Flajolet became Algorithmix—the big guy in the middle of course. Indeed, more than his development of particular algorithms, one can credit him much toward the development of algorithmics as a professional discipline: the analysis, average-case behavior, and combinatorial underpinnings of algorithms.

Here is one comment from a colleague of his at INRIA, Guy Fayolle:

INRIA has lost one of its greatest scientists. I am really shocked by this brutal and early passing away. Philippe has been my friend for some 30 years, and also a co-worker. Beyond his exceptional ability in sciences, he was also a human and jolly good fellow, with an indefatigable sense of humor. He has been a persistent defender of science against bureaucracy. We wrote several papers together, and were in the process of starting a new one—about the holonomy of generating functions counting lattice walks in the quarter plane. Philippe’s mathematical culture was immense.

The INRIA Annoucement

Here is the official announcement from INRIA—it is in French and below is Ken’s fixing-up of Google’s translation into English:

Philippe Flajolet: `Algorithmyx’ has left us!

We are deeply saddened to inform you of the passing of Philip Flajolet, which occurred on Tuesday, March 22.

Invited to INRIA in 1971 to join the group of theoretical computer science led by Marcel-Paul Schützenberger and Maurice Nivat, this internationally renowned researcher, elected member of the Academy of Sciences in 2003, ranks among the pioneers of the institute. In 1976, he directed his work towards the performance analysis of algorithms, and created with Jean Vuillemin the Algo team, which is still going strong today. Algo become a mainstay of INRIA, as it is true that “the algorithms are everywhere” in the areas explored by the Institute.

Philippe Flajolet advanced without compromise a mathematical research program targeted directly to the most complex issues raised by industrial or third-party activities. Following close upon the pioneering work of Donald Knuth in algorithms, he gave his work a clear philosophical stamp: abstraction creates simplicity. The mobilization of this research was primarily organized around the theory of approximations. He strove to achieve feasible performance, and to create systems that run quickly with rare and manageable error, rather than following past practice of privileging procedures that run surely but slowly. He brought this mode of creative solving to difficult questions concerning the analysis of the realistic complexity of algorithms involved in many areas, such as compilation, searching and sorting of information, databases, multidimensional research problems, communication protocols in networks, effective algebra, and analysis of texts.

This researcher’s scientific ambition remains oriented toward theory. He created a unified theory, analytic combinatorics, which provides access to quantitative properties of many types of discrete structures of large sizes. He achieved a kind of synthesis drawing on formal models of computing, classical combinatorial analysis, elementary complex analysis, asymptotic analysis, and some pieces of probability theory. Thus virtually all of computer science was represented in his portfolio, and his work has profoundly changed the face of this discipline to permit better understanding and better assessment of its extreme complexity.

Inveterate smoker, scourge of administrative rigidity, and herald of the cause of researcher independence, the man they nicknamed “Algorithmyx” during the heroic era of the famous INRIA “Building 8″ which hosted Algo, he carried out his quest within the ambit of this institute. He conveyed to his students and bequeathed to the scientific community several reference texts, whose simplicity, however, will almost certainly escape most of our readers!

This is actually from CodeSource, the 40-year weekly journal of INRIA.

A Personal Story

I, Dick, when an undergraduate, ran across a beautiful result of the famous mathematician Paul Tur{á}n, which stated:

Theorem: Suppose that for all {s} with real part greater than {1}, the partial sum

\displaystyle  \sum_{n=1}^M \frac{1}{n^s}

is always non-zero, for {M \ge 1}. Then the Riemann Hypothesis is true.

Call the conjecture that these partial sums were always non-zero Turán’s Conjecture. I recall thinking about this conjecture quite a bit, but of course made no progress on proving it, since it implies Riemann. It was not a waste of time, since I learned a good deal of mathematics in trying to prove it.

For some reason, I started to think about the question again in the early 1980’s, and I was unaware that the great number theorist Hugh Montgomery had proved, in 1983, that Turán’s conjecture was false. Actually Montgomery proved that even weaker conjectures were false. Before thinking again too much about the “conjecture” I asked Flajolet what he thought, by e-mail. I am sure he did not know about Montgomery’s theorem. He knew a lot about such sums. A lot. I received an e-mail in a day that proved there were counter-examples to the conjecture. Actually he computed counter-examples for me for several small values of {M}.

From Algorithms to Generating Functions

What we meant by Flajolet’s discipline and ideas above is exemplified by this paper with G. Nigel Martin, Probabilistic Counting Algorithms for Data Base Applications, originally FOCS 1983 and then journal version in 1985. The abstract begins:

This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned.

This captures all the main ideas of streaming algorithms, and indeed the Wikipedia article on them credits it and a 1980 paper by Ian Munro and Michael Paterson as being the precursors of the famous 1996 paper by Noga Alon, Yossi Matias, and Mario Szegedy, which won the 2005 Gödel Prize. Moreover, Alon, Matias, and Szegedy say in several places that they are building on Flajolet-Martin.

On this side of the Atlantic, many students in algorithms courses see the name of Dick’s old friend and colleague Robert Sedgewick on their textbooks: Algorithms in C++, or in Java, or in C, or in Modula-3, or just Algorithms by itself. However, for analysis of algorithms, Flajolet became an indispensable co-author, on Analytic Combinatorics.

However, this work with Sedgewick is new and pathbreaking—and readable for free: here. The main idea is to find representations via generating functions for mathematical objects, representations that allow tools from mathematical analysis to yield algorithmic consequences.

Generating Functions

At its simplest, a generating function describes an infinite sequence of numbers {[a_n]} by representing the single-variable formal power series

\displaystyle  \sum_n a_n x^n.

For example, if we have the trivial constant~1 sequence, i.e., {a_n = 1} for all {n \geq 0}, then we want a finite representation for {\sum_n x^n}. We can get one uniquely via the identity

\displaystyle  \frac{1}{1-x} = \sum_n x^n.

This is numerically valid, even over the complex numbers, provided {|x| < 1}. If we want the alternating sequence {1010101\dots}, we use

\displaystyle  \frac{1}{1-x^2} = \sum_n x^{2n}.

It is similarly easy to see that {1/(1+x)} gives rise to the sequence {1,-1,1,-1,1,-1,1,\dots}. Now let’s try a far less obvious example. Index the Fibonacci numbers by {F_0 = 0}, {F_1 = 1}, {F_2 = 1}, {F_3 = 2}, and so on. Then we have:

\displaystyle  \frac{x}{1 - x - x^2} = F_0 + F_1 x + F_2 x^2 + \dots.

We can view the left-hand side as a particularly succinct representation of the right-hand side. Now the point is that one can analyze and operate on these representations, to achieve deep insights. When we say “one,” we mean mathematicians like Bob and Philippe who can use tools from analysis to make these generators yield beautiful insights. See their book for many examples of the amazing power of this method.

Probabilistic Counting

One sample paper of Phillipe, joint with Marianne Durand, is this gem, with the neat abstract:

Using only memory equivalent to 5 lines of printed text, you can estimate with a typical accuracy of 5 per cent and in a single pass the total vocabulary of Shakespeare. This wonderfully simple algorithm has applications in data mining, estimating characteristics of huge data flows in routers, etc. It can be implemented by a novice, can be fully parallelized with optimal speed-up and only need minimal hardware requirements. There’s even a bit of math in the middle!

The algorithm is called the {\mathsf {LogLog}} algorithm. The paper employs both an exponential generating function and the streaming analysis of Alon-Mathias-Szegedy, which it cites. This is the “math in the middle” part. Thus it synthesizes the above theoretical ideas in an application.

Here is a figure that gives another view of the algorithm:

Open Problems

The main open problem is, how do we further a person’s life work? The work itself is young—for example, the text with his close friend Sedgewick has lost one parent at only two years old.

We will be happy to receive suggestions on how further applications of this material can be developed, ranging from third-party applications to our own previously expressed interests in approximate counting as a tool of theory.

Again the passing of Philippe Flajolet is a great loss, and our thoughts go to his friends and family.

[added more from Dr. Guy Fayolle after the `---', and with thanks to him]

About these ads
11 Comments leave one →
  1. March 27, 2011 7:45 pm

    Alas,sad for his passing away,I have read analytic combinatoryics by him,it is surely a elegant book.

  2. Sylvain permalink
    March 28, 2011 8:32 am

    A great and saddening loss indeed.

    Just a side note, the version of the cartoon you present at the beginning has an extra character on the right (legionnaire quipeuleplus) which does not appear on the cartoon in Building 8 (in which I’m sitting right now).

  3. March 29, 2011 7:43 am

    All automorphic forms or functions are generating function,and automorphic forms or functions play a key role in modern math,such as zeta function or Eisenten series.I guess, automorphic forms or functions may also play an important role in computability theory ,but we or at least I have not found any concrete connection between them.

  4. March 29, 2011 7:53 am

    a famous example is counting and modular form ,a special case of automorphic forms ,that is Taniyama-Shimura theorem,which displayconnection between the number of solutions of a kind of diophantine equation and modular function

  5. March 29, 2011 7:42 pm

    This is so sad. Philippe was both a brilliant researcher and a wonderful character.

  6. Pierre permalink
    March 30, 2011 2:25 pm

    He as also a wonderful teatcher. I remember one of his story: A space traveler arrives at a new planet and wants to know how many days there are in a year. But he dosen’t want to ask. Then he asks people their birth dates and an estimates the result by examinating the collisions.

  7. April 4, 2011 10:10 am

    What sad news. My own connection with Philippe Flajolet was slender: he saw a simple paper of mine in a journal and promptly recognized a breathtaking generalization–a typical example of this man’s analytic virtuosity, which bridges discrete and continuous mathematics. No single set of collected works in computer science will have more lasting value than Flajolet’s.

  8. Xrma permalink
    April 6, 2011 10:41 pm

    I felt very sorry about this great professor, his book “Analytic Combinatorics” gives me a lot of happyness!

  9. Kevin Compton permalink
    April 19, 2011 2:33 pm

    I had the good fortune to spend a sabbatical year in Philippe’s group at INRIA twenty years ago. Philippe liked to arrive mid-morning and work late into the evenings. Around 10 a.m. he would enter, sweeping down the hallway of Bâtiment 8, knocking on doors and yelling “café.” We would assemble in the small coffee lounge to chat and exchange gossip. Philippe would station himself, smoking and drinking coffee, next to the printer and from time to time look at the emerging documents, often drafts of conference and journal papers being prepared by the researchers. He would make remarks such as, “Ah, Abel sums. You know their relationship with the Ramanujan Q-function, of course.” Of course you didn’t, but you listened carefully because you had probably missed something crucial. He would then offer you a paper he had written on the subject. A couple of weeks later he would come to your office and say, “you will give a seminar on the Abel sum work you are doing?” In the time I was there, we never had a formal staff meeting of any kind, but he had a better handle on the activities of his group than any other project director I’ve known.

    Another story, because I can’t resist: The first time I visited INRIA Philippe picked me up in his car from the Versailles train station. As we approached the INRIA front gate he said, “they will want to hold your passport – just hold up something.” Passing the guardhouse, without slowing down or looking at the guard, Philippe held up his INRIA badge. I held up my University of Michigan ID. As we rounded the small traffic circle inside the gate I saw the guard do a double take and stare in a bewildered manner at the back of Philippe’s car. “He has very slow reflexes,” Philippe explained. “This usually works.”

    Generous, droll, sage, irreverent, he was un vieux ami, un vrai ami. I will miss him.

    • April 19, 2011 9:52 pm

      Nice stories—thank you very much, and to everyone who has posted here. I myself unfortunately did not talk long with him at the conferences in the 1980’s where I met him.

      A reminder that only your first comment enters the moderation queue—after that, things work in real time…

  10. Tony Guttmann permalink
    May 26, 2011 3:19 am

    A great loss. Not only a wonderful mathematician but a lovely man. In 1996 he came for dinner to my apartment when I was on sabbatical in Bordeaux absolutely laden with things he thought I must try – from Bordeaux wines to Vacherin du Haut-Doubs cheese. Recently I had a tricky asymptotics problem based on work I was doing with my PhD student Nick Beaton. As we were getting nowhere, I suggested we send it to Philippe. He wrote back in mock abuse — he was a guest lecturer at Institut Poincare, and found our problem much more interesting than the lectures he was supposed too be preparing, and so abused me for sabotaging his lecture preparation. The results of this work are shortly to appear in J Comb Theory, where the write-up displays the unmistakable stamp of the master. The best legacy anyone can have is that the world is richer for their passing. Philippe was such a man.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,917 other followers