Prof. Philippe Flajolet (December 1, 1948 -March 22, 2011) is a leading French computer scientist. He received his Ph.D. in 1973 in computer science from University Paris Diderot and state doctorate in 1979 from Paris-Sud 11 University. He devoted his life to the general method for analyzing the computational complexity of algorithms. He introduced the theory of analytic combinatorics. He was elected a member of French Academy of Sciences and Academia Europaea. The HyperLogLog commands of Redis are prefixed with “PF” in honor of Philippe Flajolet.

HPL: Maybe I shall explain first who will be the targeting audience of this interview. This is kind for popular science journals. Basically our readers range from high schools students, teachers and all kids who are interested in mathematics.

PF: High school students or high school teachers?

HPL: High school students, teachers and all the kids who are interested in mathematics.

PF: Great. That’s wonderful.

HPL: We usually start with questions asking how you became interested in sciences or how it was developed.

PF: That’s an interesting question. Well, actually what was important for me was that my parents were adults during World War II and they did not go very far in their studies, not much beyond secondary educations. But my grandfather was an astronomer, in Lyon, the city that I was born in. He died shortly before I was born and also my grandmother was a high school teacher. So while I was flocking around, there were some values for intellectual activities. When I was a kid in the attic, there would be math books, physics books, science books, books about observations of stars and these other things, so for me there was always an aura of mystery. Later I encountered colleagues and former colleagues of my grandfather’s, like the director of the observatory and others. So in a way there was always an atmosphere that science was something, at the same time, a little bit mysterious perhaps. But it was something that had value, and certainly more than commercial activities or banking or financing and etc. . So I think that explains my inclination to do science.

HPL: So you went to school in Lyon?

PF: Yes, Lyon was where I was born. I was lucky enough to get admitted to the good schools there which were all state schools, not private schools, and they were extremely well managed. When I was about thirteen, a professor who had studied and got his higher education in École Normale Supérieure, which was normally, trained research mathematicians, but, he had decided to become a secondary school teacher. There was obviously a very strong flame in him about mathematics. He was deemed by many to be too difficult or whatever, but, I have from him a strong motivation for mathematics and that he played a very important role for me between the age of 12 to 15. Also he had been one of the proponents in reforming new mathematics for high schools, which turned out to be quite bad at the end. But introducing more of logic and set theory and formalization into secondary education, except in his case, as one of the original proposers and he knew lots of what’s behind, and he was able to do both the formal side and making it inspiring also.

HPL: The reform you have talked about, when was that?

PF: No, earlier than that. 1960s probably. I graduated from high school in 1966. So the reform started probably in the early 60s. It went probably as far as mid 70s or early 80s and it was somehow watered down.

HPL: Almost in the same periods of what happened in the United States or what happened in Taiwan.

PF: I am not too knowledgeable about secondary education of United States or here. What I can say at least about these reforms was that it was certainly influenced by the Bourbaki movements---I mean, mathematicians like me in the applied mathematics---I am not too much inclined in this direction. I can understand there were some goods, but there were some excessive also in this period in the area of education, I think, towards excessive formalism. So I was happy enough and lucky enough that in my case I have both the formal and intuition behind, you know, presently joint together. But the thing propagates to people who have less understanding of what was behind, so this lead to excessive formalization and there were some back tracking, perhaps too much back than nowadays in some cases. I mean perhaps too much pragmatic, non-proof like attitude to mathematics which is related.

HPL: You said secondary education that means from the age of 12 to 18 years old?

PF: Yeh, from 12 to roughly 18. It’s sort of hard because the category is not exactly the same. We have what we called lycée of French or in German Gymnasium at that time which goes from about 11 or 12 to 18, when you graduate and then enter an university. So there was no college system as opposed to US.

HKH: During some time, you were much interested in linguistics?

PF: Oh yeh, that came, I have really excellent teachers and I was on a special track in school. I had also excellent teachers in literature and classic languages. When I was probably about 13 or 14 years old, one of them gave examples which were very revealing about connections between various languages of Europe, so the family of Indo-European languages. At the time, I was already interested in Sciences, Mathematics and Physics mostly. But then I did little bit of digging and reading and sort of discovered that there were a lot of regular structures in the so-called morphologies of natural languages. For Chinese, that is a bit different because you don’t have case ending and conjugations. But Europeans languages like the ones I sort of knew like Latin, English, and Russian, possess some amount of morphologies. Then you look at this and sound changes, there were a lot of incredible regularities and actually linguistics there was these structured movements in 1900 which I found sort of, having a mathematically inclined mind, something that is very attractive by its regularities, its rigor and the fact that you look for the shape also. Perhaps as opposed to people who view mathematics as formal exercise while you ground up proofs, I mean here you have to find structures, but it’s sort of recognizing or detecting shapes or regularities or things like these, which you are very much comparable to what shall be created in mathematical activities. So for me, perhaps it’s … , you have young readers, for me, well in teaching one has to go through the stage of formal proofs and certainly you need to acquire all the skills to do that. But in the end, as a research mathematician, you need the ability to see shapes, create shapes or structures and the activities of research mathematicians in this sense is sort of different from that one encountered as a teenager at the school.

HKH: So from natural languages to computer programming language? So is that a natural shift?

PF: Ah… Of course, because I recognize myself as a mathematician, but I guess I am sort of half breed of mathematician and computer scientists and not sure exactly where I am at times. Actually when I was studying in École Polytechnique the emphasis at the time was largely on real analysis, not completely, but largely,

HKH: Because of the Bourbaki influence?

PF: Well, no, Laurent-Moïse Schwartz was there although he was not a teacher of my year. Probably, certainly because of the influence of Laurent-Moïse Schwartz, but also who was the founding father of the theory of distributions, but also because there was the idea at the time that mathematics shall be alongside the needs of mathematical physics and physics itself. So, that was not placing a strong emphasis on discrete mathematics. At the time of I was studying at Polytechnique, I was sort of contemplating the possibility of doing something more to it formally. I mean linguistic theory, formal language and all that. So it turned out they offered courses in mathematical logics which were going in this direction and encountered my Ph. D. adviser at that time Maurice Nivat, and eventually I got my first position as sort of a research assistant, who lives in through that channel.

HPL: I see. You studied at Polytechnique, then afterwards you went to Paris-Sud 7 University?

PF: So eventually I got my Ph.D. in Thesis from Paris-7 in 1973, the point being that at the time, the Polytechnique was not granting Ph.D.s. So it was. So I finished the Polytechnique, then I took sort of a master course and got my Ph.D. about three years after that. So that was fairly standard course of events at the time. But I was lucky enough to be already hired as a research assistant but we were already quite independent by my current institution in INRIA. There perhaps something worth mentioning is I was recruited into this position by my thesis advisor at the time, then I joined a school, the French School of Theoretical Computer Scientists, that was around 71 or 72, so everything was still, in retrospect, 40 years ago and beyond. There was a fairly well-formed school of theoretical computer scientists based largely on the theory of formal languages and automata and their leading figure was Marcel-Paul "Marco" Schützenberger who actually wrote on formal linguistics and worked with Noam Chomsky, the famous linguist from MIT, and now a famous political activist as well.

HKH: Then switching from programming language to more analytic structures?

PF: Okay, so I made a start more on the side of formal grammar and automata, so it’s sort of this part of computer science that interests in what is a priori decidable or what is remained undecidable. I got my Ph.D. in that. Then for me I think this area is a little bit dry. So I guess some people have in mind to do research in logic, some to do in algebra, I was happy that as a student I have read a very good French book by a Frenchman on combinatorial analysis, someone named Louis Comtet, I mean his book is still in the national reference nowadays. The English title is “Advanced Combinatorics”, and the French title is “Analyse Combinatoire, Tomes I et II”, two small volumes about 150 pages each. I remember reading these on the beaches of Adriatic during holidays when I was still a student. So I sort of have this love for combinatorial analysis as it’s called, but no occasions to practice it. When I finished my Ph.D. there came back a guy from Stanford who was a year older than me, whose name was Jean Vuillemin. At Stanford he has done his thesis a little bit like me in semantics, but he was under the strong influence of somebody who was and still is a giant in the field, Donald E. Knuth, the founder of TeX, so Jean Vuillemin came back from Stanford full of research ideas about analysis of algorithms which I knew very little about. Then I discovered that sort of my true love which was Combinatorial Analysis, that is very relevance to understanding the behavior of performance of algorithms. That was around 1975 or 1976.

HPL: Is the professor for real analysis Gustave Choquet?

PF: Yeh, at the time of my studies, I have courses taught by Choquet in general topology and real analysis, but general topology mostly. I was also lucky to have Jacques Neveu who was a well-known probabilitist and a superb teacher on the analytic side and he was teaching integration measure, probability and introduction to probability.

HPL: You have a very solid background in mathematics.

PF: Yeh, in the Polytechnique it’s a very strange institution. It used to be school training for engineers and transformed into school training for artillery officers under Napolean. In two centuries later, it is still a school under military administration because of that. But it reverted to more civic activities but then a lot of courses were taught by very great mathematicians so it has a very complicated historical situation, but basically, yes, you get a very good training, it’s a very good school.

HPL: Are all the students admitted into Polytechnique very strong in mathematics and physics?

PF: Yes, the entrance examinations are based on mathematics and physics.

HPL: Only these two subjects?

PF: Well, no, there are also a little bit of chemistry, languages and extra, but the weighting of the various disciplines, give variance of math and physics, then you can enter more or less under two different tracks: one with math major and physics secondary major and vice versa.

HPL: May I go back to the high school education, do you have courses in philosophy or something like that?

PF: That’s a very interesting question. Of course I am not too knowledgeable about what happens nowadays, almost an old man, but in my time, in a classical high school, we would have at least 6 years of Latin and also 6 years of French, meaning language, literature and history of the language. That would be the main activities for the first four years of high school and math would come second because that activity I am describing would include Latin and French. So you would say sort of Latin, French and Math would be of equal basis. Then after four years of that system, you would switch to a more differentiated system where you could opt for something more oriented towards languages and literature, or math and fundamental science or so-called experimental sciences and that would be a three year track. Nowadays, this situation is more complicated because a lot of tracks and professional tracks have been introduced and this sort of classical education has started to fade out or diluted.

HPL: You have to write test or thesis or small thesis for your courses in high school?

PF: So for literature, it would be either analysis of text, in my time also, we would be taught some ancient French, so that would be systematic things on grammar, the logical analysis of sentences which I found where to be an excellent training for the first two years. Then there would be more about interpretation of texts, commenting on texts, whether contexts to be historical or literally context things. Then this would become less important for people, who like me choose mathematics, then mathematics would take over and I would say unfortunately, we have philosophy at the last year of the high school and only probably about two hours a week. But I have very good memory of it. The professors were really interesting. They tried to evoke some ideas about Epistemology, history of sciences and all that which I think it was all of awakening. But there was probably too little philosophy.

HPL: I see. I am wondering if this has any impacts on your later career or later thinking.

PF: Certainly, this sort of more classical education certainly has a lot of impacts. Latin is sort of the opposite of Chinese so it has highly inflected forms. So you need virtually a logical brain to assemble what goes with what, etc. . My training has a lot of these, I really understand deeply mostly about the syntax. Now they say there are some people who finishing high schools that have difficulties in fluent reading. Well, in my time we are doing digging reading deep in the first few years, which I thought was very good. The philosophy I think was important and probably was important to everybody but I was not so keen on the side that has to do about commenting literature and literary. I mean comparing this author and that author and the context.

HKH: But that is one aspect which is more visible, when you often write papers that are more readable with clear presentation and conclusive ideas.

PF: In this respect, perhaps the classical training helps. But I must say this friend I mentioned, Jean Villemin, together with some of the fellow young scientists we would see passing by in this nascent discipline of computer science coming from the US, those people brought a different style of writing. So, of course, I grew up in a style that is a little bit formal, and certainly in retrospect, too formal, because French schools in the 60s. Still today you find mathematical papers that do not explain why you could be interested in the problem, that do not offer sort of an opening on future work or conclusion at the end. That won’t summarize the major ideas, so you get sometime the ideas which is wrong of course to be good mathematics, but you get the crank of it. Fortunately from the Knuth school which had a well-established tradition of trying to write well and concrete ideas I think I got this influence.

HKH: So from the 1970s to now, the theoretical computer science community in France has developed into a very active stage, can you describe roughly how does it evolve?

PF: Alright. So, in the 70s, I would say most of the theoretical work about computer science was about models of computations or formal models. Automata Turing Machine plus some idealization of that, but the question there was what could you describe with that or with restricted devices and what are the formal capabilities. Then I think the later 70s early 80s in France, the development of people like myself trying to take into account the notion of complexity. So notion of complexity is not only something utilitarian, like a cost you have to pay for machines to do so many instructions, but I think it’s also conceptual, obviously certain property or deeply hidden in objects and still that’s something we don’t understand a lot philosophically and you need to do a lot in order to dig it out. So the notion of complexity became important in the 80s and that sort of developed into a new school with algorithms. In my own experience also we had people around me interested in computer algebra, so we gradually became interested in that, either as a tool but also as a subject in itself. So that leads to further sophistication in the 90s. Now there is a whole tree of activities at the interface between mathematics and computer science. You could call this theoretical computer science which I think sometimes suited more which include computer algebra, computational geometry, analysis of algorithms, but number of things about proofs; another area which farther away from mine, which is developed from models is developing proof systems for programs and I think part of the development nowadays in mathematical logic comes from the needs of the verifications of properties of programs in computer science. On this last aspect, for instance, about one or two years ago, scientists managed to develop a fully formal proof of the famous four color theorem which was the first complete proof written and checked by a computer and it was much less trivial than it seems. It’s highly nontrivial as it seems. It requires lot of thinking about the proof, but it also requires a lot of intelligence on the part of the people who have developed this proof system, so that you can really access a technically very difficult problem and actually verifying it with one such a system.

HPL: Is there a possibility that a computer will take over the job of mathematician?

PF: Ah … that’s … personally I think not, but there are a lot of jazzes in the US started in the 60s about artificial intelligence and they claim that they would solve everything … well .. things are … I think we human have a lot of capabilities of reflecting, building new frameworks and of course we can get useful help from the computer but it’s just a tool and I adventure to say that in a hundred years from now of course we would get a lot more held but I think we human shall be there. Actually there are foundational results that tell you for instance you can have computers checking things when I was referring to the Four Colors Theorem but you need to have the human working with a computer to actually, human forming the steps and having computers being able to sort of follow the steps, we are not talking at all the computers being creative in anyway. So it’s a very intelligently designed computer software to put in use again by human so you have the human thinking of the proof knowing what a computer can do, preparing, formalizing, at the same time developing the tool and I think this would stay this way for many decades at least. I don’t vision computers have possibilities of creating new frameworks.

HKH: There are also a few areas in mathematics like probability, statistics that you have more close contact with.

PF: Yes, that’s right. Now we are coming back closer to the type of things that interest Hsien-Kuei and me. For the purpose of understanding complexity, complexity was for a long time, in the 80s to mid-90s, thought of what happens and what is the worthy value. So you want to do a computational task and usually for this computational task you want to measure the cost, called this complexity for short. That cost depends on the size of your data, so we have a certain complexity function and a complex problem with a high complexity function, of course. So for a long time people are considering complexity problem as the worst case. What’s the worst scenario if you want to sort cards? It turns out and that has been thought by all the people like Knuth, Michael O. Rabin once was between Harvard and Jerusalem (Hebrew University). It had been realized what’s really relevant is what happens in probability. It’s much more important. So if you want to sort data, you are not slightly interested in what happens, if you have a demon that knows the method you are going to use, and these are the things most embarrassing, but what happens if you take your method and apply to casual data, like names of people on the street. So that means you are interested in not so much the worst case but so-called the average case scenarios and you are also interested in what happens with high probability or with a fair probability. Then this area of understanding the complexity of algorithm sort of comes in natural contact with several areas with probability theory. The ones that have to be do with essentially discrete, random variables and discrete models. So there are a lot of contacts and exchanges nowadays in the area of understanding analyzing algorithm, understanding their probabilistic behavior is a strong, I would say factor, in developing the study of these random discrete structures, like random graphs, random permutations, random strings and etc.. So in any case, you know almost all that, certainly the historical aspects.

HPL: Do you think that mathematics is like a language? I mean a lot of kids have problems with mathematics, but if they could think mathematics just some kind of languages. Would it be easier for them? This has just come to me.

PF: I am not sure. In a certain sense, mathematics is a language because it helps you to formalize a lot of things in physical world or understanding situation, humans and all that sort. But I think the reasoning aspect and putting shapes is very important. I view mathematics as a way to train the human mind to treat complex structure and entretenir complex relationships. So you should learn to reason within mathematics, not just view it as definitions. Of course, definitions are useful and important. But I think solid conceptualization has great help to conceptualize to think of structures of the world, the society or whatever. I think you look at society or economy in a different way if you have a math training or you are trained as a lawyer. Something very positivist in what you can gain if you look at these things.

HKH: So if time went back to 40 years or 35 years or something, would you still choose the same path?

PF: Now, in many ways, I think that I was very fortunate. Some of the decisions were not really mine to start with. So first of all, there was the École normale and École Polytechnique. Both are Grande École and being competitive. I was very pure when I sat for the exams. But I must say that much to my shame I missed the École normale on the first try and I did get into École Polytechnique without much difficulties so I entered the École Polytechnique which was perhaps not my first choice. It was my father’s first choice. Kids there are shortly to have a good job. Then I was there, shortly after the 60s movement. I didn’t feel like being, all the time, and military administration so I didn’t take too many courses. I skipped most of the ones which I was not interested in. This also means that I didn’t want to go to what was locally considered as main stream channel to research, so, in a sense, I diverted from mathematical analysis although that was what I liked at the time. This divert from mathematical analysis because you would say because of the context at the time. Then this interest in natural language which has been accidental surfaced and helped me got into formal linguistics closer to computer science then I also took courses at the time in university in logic and decidability theory. I had been promised to drop by a professor but he didn’t keep his promise. So I turned back to theoretical computer science without knowing any computer science, but few people knew at the time anyhow. Then the professor just had for myself, a friend of mine with my working said: “Oh, I have two positions in the institute etc., are you interested?” I have never heard of the Institute but that was the only possibility so I jumped there. It was called IRIA at the time, now it is called INRIA. So I got the position without much difficulty. Then I land there and there was this person called Marko Schützenberger and actually I had read about him before not knowing I would encounter him a week later. It was sort of a far-west sort of things. Nothing was well established. There was no hierarchy. Everybody was between 20 something and 35 something and the field did not exist before. So I think I was very very lucky. With the succession of accidents but I was lucky. I mean your taste play a role and what helped also it to develop your own taste and let yourself be influenced by the right people.

HPL: So you stayed in Paris all the way?

PF: Yes, so I still worked there 40 years later in that same institute which had hired me in the first place.

HPL: I am very sorry that I am not in your field so that I can only ask questions as in general. Well, what kind of suggestions you would give to young students who are interested in science?

PF: Oh, that. I think in science is a wonderful experience. It’s a wonderful way to develop. Not your brain in a technical sense, but I mean your personality. So if you like science, go for it, love it, and study it, not necessarily in a traditional way. Develop your own tastes, do your own reading, choose the books which you want to buy and buy them, browse through them, read popular science magazines if you wish, trying of course with the web, try to pick up things, develop your own micro research project even it’s wrong it doesn’t matter, explore your ideas and I think in my case, I also saw that if you look at the boundaries between mathematics and theoretical computer science then if you keep your eyes open, there are a lot of interesting problems that come from the outer areas. So if you are interested in more applied things, look at what happens in physics, engineering, information sciences?

HPL: Thank you for sparing your time to doing this interview with us today.

• Hsien-Kuei Hwang is a faculty member at the Institute of Statistical Science, Academia Sinica
• Hsuan-Pei Lee is a faculty member at the Institute of Mathematics, Academia Sinica.