Philippe Flajolet was a Computer Scientist who is known for his work on Probabilistic Counting Algorithms. His active area of research was Time Complexity of Algorithms and Analytic combinatorics. He had coined the word "Approximate Counting".
He was originally from Paris, France.

Algorithms developed by Philippe Flajolet:

• Flajolet Martin algorithm in 1984 by Flajolet and Martin
• LogLog Data Structure by Marianne Durand and Philippe Flajolet
• HyperLogLog Data Structure by Philippe Flajolet

The importance of his work on Probabilistic Counting is understood from the fact that the first algorithm to improve over the naive approach was introduced by Robert Morris in early 1980. Following this, Flajolet analyzed the problem fully, introduced key data structures in the domain that are in use even today and coined the word "approximate counting" for the field.
Philippe Flajolet is considered as the father of Approximate counting.

He was born on 1 December 1948.
Education of Philippe Flajolet:

• Ecole Polytechnique
• PhD from Paris Diderot University

He co-authored a book on Analysis of Algorithms along with Robert Sedgewick. With Robert, he worked on several problems like 100 prisoners problem.

Flajolet held the following Professional positions:

• Member at French Academy of Sciences
• Member at Academia Europaea
• Research Director at National Institute for Research in Computer Science and Automation (INRIA)

He died on 22 March 2011 in Paris due to unknown reasons. This was an unexpected event and came as a shock to his fellow researchers as his health was good.

Personal Life

Philippe was always seeking to dive into new research. Whenever he read a paper and found it to be interesting, he would note the authors and find them at a Conference. When he meet them, we would discuss some ideas and extend an offer to work at INIA where he was a director.

This would be followed by an intense exchange of ideas and would result in a research paper.

People who have worked by him have said that he viewed a problem from the point of history of evolution of algorithms. To give you an idea:

• In 1960s, each bit was a seperate device so there were around 1000 bits in a computing system. Papers were typed by secetaries and interaction with a computer was through punch cards.
• In 1970s, bits were being automated in Integrated circuit devices so it millions of bits were accomodated in a system. Humans communicated with computers using CRT terminals. Everyone used word processing systems and typed their own papers.

These changes had a profound impact on Philippe. He was involved in making Computing a science. In 1970s, people were deciding if Computing should be given a status of a scientific domain.

Donald Knuth spent a significant amount of time researching on various aspects of Computing and demonstrated that it deserved its very own research direction. Flajolet contributed greatly to this by studying Knuth's work and developing his own research on the analysis of Algorithms.

Philippe Flajolet was one of the key figures along with Knuth to help make Computing a science. He was a great mathematician as well which is evident by his in-depth analysis.

His grandfather was also named Philippe Flajolet (1885-1948).

Philippe gave this Happy New Year 2009 card to his well wishers:

Philippe Flajolet Lecture Prize

Philippe Flajolet Lecture Prize is awarded every 2 years to Researchers with outstanding contributions in the field of analytic combinatorics and analysis of algorithms.

This is in memory of Philippe Flajolet and his legacy. This is awarded by Analysis of Algorithms (AofA) community which was started by Flajolet.

The winners are:

• 2014: Donald Knuth, Professor Emeritus of the Art of Computer Programming at Stanford
• 2016: Bob Sedgewick, William O. Baker Professor of Computer Science at Princeton
• 2018: Luc Devroye, James McGill Professor of Computer Science at McGil
• 2020: Wojciech Szpankowski, Saul Rosen Distinguished Professor of Computer Sciences and Professor of Electrical and Computer Engineering at Purdue

Next winner will be declared in 2022.

Research Papers by Philippe Flajolet

Last Research Paper was in 2011 titled "On Buffon Machines and Numbers" by Philippe Flajolet, Maryse Pelletier, and Michele Soria. This was published in ACM-SIAM on Discrete Algorithms (SODA).

You can read about it here: http://algo.inria.fr/flajolet/Publications/FlPeSo11.pdf

The most impactful and interesting Research papers by Philippe Flajolet were as follows:

• 2010: "The distribution of height and diameter in random non-plane binary trees"
• 2009: "The Number of Symbol Comparisons in QuickSort and QuickSelect"
• 2007: "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet, Eric Fusy, Olivier Gandouet and Frederic Meunier
• 2006: "The ubiquitous Digital Tree"
• 2003: "Loglog: Counting of Large Cardinalities"
• 1999: "Properties of Random Triangulations and Trees"
• 1998: "On the Analysis of Linear Probing Hashing"
• 1998: "The Analysis of Hybrid Trie Structures"
• 1997: "An average-case analysis of the Gaussian algorithm for lattice reduction"
• 1993: "Analytic Variations on Quadtrees"
• 1993: "The distribution of heights of binary trees and other simple trees"
• 1992: "Varieties of Increasing Trees"
• 1992: "Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-organizing Search"
• 1991: "Automatic average-case analysis of algorithms"
• 1990: "Average-Case Analysis of Algorithms and Data Structures"
• "Random Tree Models in the Analysis of Algorithms"
• 1986: "The Analysis of Simple List Structures"
• 1985: "Probabilistic Counting Algorithms for Data Base Applications"
• 1985: "Approximate Counting: A Detailed Analysis"
• 1982: "The Average Height of Binary Trees and Other Simple Trees"
• 1980: "Dynamic Data Structures: Fiite Files, Limiting Profiles and Variance Analysis"

Quotes by Philippe Flajolet

Following are the popular quotes by Philippe Flajolet said at Conferences:

• "If you can specify it, you can analyze it."
• "I can count in less memory if you do not want exact answer."

View a lecture by Flajolet

With this, you have a good idea of the legend in Computer Science, Philippe Flajolet. Enjoy.