Through my career, I have delivered over 100 invited talks around the country and around the world. This page includes abstracts and the slide presentations for most of these talks. Many of the talks evolved over several presentations—the slides here are the most recent.

You can clearly see the evolution of the quality of presentation materials in this content. For many years, presentations were handwritten on vugraphs or even chalktalks because including mathematical equations and figures was just too difficult. In some settings, spontaneity was encouraged—at early Dagstuhl seminars, for example, people were encouraged to not make their slides until the night before the talk! So, you can expect to find plenty of bugs in the early talks.

Why not post videos of the talks? This will likely be the norm in the future, as people gain experience with the video production workflow, but my feeling is that videos taken from the back of the room, as has been typical, are rarely worthwhile.

Some of the information in these talks is also found in research papers or books, but much of the content is uniquely present in the slides. While these are hardly authoritative sources, many people have expressed interest in this content.

2023 ESA Test-of-Time Award

LogLog Counting of Large Cardinalities
Marianne Durand and Philippe Flajolet

Abstract

This 2003 paper introduces an approach to solving the cardinality estimation problem, a fundamental problem in data science. It meets the test of time because it is a simple, elegant and efficient algorithm; it is a poster child for both analytic combinatorics and algorithm science; and it is broadly applicable and widely used.

Venues

2023 European Symposium on Algorithms, Amsterdam

What do we know about Quicksort?

a brief summary of facts learned since the 1960s

Abstract

Many computer scientists might be surprised to learn that the study of Quicksort has remained a vibrant area of research since the algorithm was invented. A surprising number of theoretical questions have been resolved, and our understanding of how best to adapt the algorithm to important practical applications has expanded considerably. This talk, prepared on the 60th anniversary of Tony Hoare’s invention of Quicksort, briefly summarizes some of the important results of that research.

Venues

2021 Issac Newton Institute, Cambridge, UK (virtual)

A 21st Century Model for Disseminating Knowledge

Abstract

In the early years of the third millennium, most professors are still teaching in virtually the same way they were taught and their teachers were taught, stretching back centuries. As we all know, this situation is ripe for change. University students seeking to learn a topic who now have little, if any, choice are about to be presented with a vast array of choices. What student would not want to swap a tired professor writing slowly on a chalkboard for a well-produced series of videos and associated content, given by a world leader in the field? We are on the verge of a transformation on the scale of the transformation wrought by Gutenburg. This imminent change raises a host of fascinating and far-reaching questions. In this talk, we describe a scalable model for teaching and learning that has already enabled us to reach millions of people around the world.

Venues

2013 Queen Mary University of London, England
2013 AofA’13, Menorca, Spain
2014 Universidad de la República, Montevideo
2014 Florida International University, Miami, FL
2015 NYU Polytechnic, Brooklyn, NY
2016 Dagstuhl, Wadern, Germany
2016 University of Utah, Salt Lake City, UT
2017 Princeton University, Princeton, NJ
2017 Georgia Institute of Technology, Atlanta, GA
2017 University of Southern California, LA, CA
2017 Harvey Mudd College, Pomona, CA
2017 University of Michigan, Ann Arbor, MI
2018 MIT, Cambridge, MA
2018 Brown University, Providence, RI
2019 The Round Table, Saint Louis, MO
2019 Universitat Politècnica de Catalunya, Barcelona
2019 University of Colorado, Boulder, CO

Cardinality Estimation

Abstract

The problem of determining an approximate count of the number of items in a data stream has a rich history, dating back to a paper by Flajolet and Martin in the 1980s. This talk surveys the useful methods that have been invented, focusing on algorithms developed by Flajolet and co-authors that culminated in the HyperLogLog algorithm. These algorithms are characterized by careful analysis validated by experimentation, and are widely used today in cloud computing. The talk ends with a proposed new algorithm, HyperBitBit, that seems to provide accurate estimates for large streams using very little computation per item and only a very small amount of memory.

Venues

2016 Flajolet Lecture, AofA’16, Kraków, Poland
2016 University of Utah, Salt Lake City, UT
2017 University of Southern California, LA, CA
2018 Knuth80 Symposium, Piteå, Sweden
2019 Dagstuhl, Wadern, Germany

“If You Can Specify it, You Can Analyze It”

the lasting legacy of Philippe Flajolet

Abstract

The “Flajolet School” of the analysis of algorithms and combinatorial structures is centered on an effective calculus, known as analytic combinatorics, for the development of mathematical models that are sufficiently accurate and precise that they can be validated through scientific experimentation. It is based on the generating function as the central object of study, first as a formal object that can translate a specification into mathematical equations, then as an analytic object whose properties as a function in the complex plane yield the desired quantitative results. Universal laws of sweeping generality can be proven within the framework and easily applied.

Standing on the shoulders of Cauchy, Pólya, de Bruijn, Knuth, and many others, Philippe Flajolet and scores of collaborators developed this theory and demonstrated its effectiveness in a broad range of scientific applications. Flajolet’s legacy is a vibrant field of research that holds the key not just to understanding the properties of algorithms and data structures, but also to understanding the properties of discrete structures that arise as models in all fields of science. This talk surveys Flajolet’s story and its implications for future research.

“A man … endowed with an exuberance of imagination which puts it in his power to establish and populate a universe of his own creation.”

Venues

2013 SODA, New Orleans, LA
2013 Université Pierre et Marie Curie, Paris, France
2013 Vienna University of Technology, Vienna, Austria
2013 CanaDAM, Newfoundland, Canada
2014 Université de Versailles, Versailles, France
2014 LATIN, Montevideo, Uruguay

Putting the “Science” back into Computer Science

Abstract

Before the advent of computing, a standard science and mathematics curriculum was developed in secondary education, supported and expanded by first-year college courses, that serves as the technical basis for every student in science and engineering. For whatever reason, we have seen two unfortunate developments at the dawn of the new millennium. First, many computer science students have somehow been exempted from having to know basic precepts of science and math (instead, they learn about developing large programs). Second, many students in science and engineering have somehow been exempted from being exposed to basic precepts of computer science (instead, they learn specific programming tools). In both cases, students are being shortchanged. One solution to both of these problems is to integrate computer science into the standard curriculum, so that all students with a general interest in science and engineering develop a common technical basis in math, science, and computing before moving into discipline-specific studies. Providing such integration early in the curriculum is easier than it might seem.

Venues

2007 Adobe Systems, San Jose, CA
2007 Purdue University, West Lafayette, IN
2009 University of São Paulo, São Paulo, Brazil
2010 Carnegie-Mellon University, Pittsburgh, PA
2010 Rutgers University, New Brunswick, NJ

Algorithms for the Masses

Abstract

Before the advent of computing, a standard science and mathematics curriculum emerged in secondary education, supported and expanded by first-year college courses, that serves as the technical basis for every student in science and engineering. For whatever reason, we have seen two unfortunate developments at the dawn of the new millennium. First, many computer science students have somehow been exempted from having to know basic precepts of science (instead, they learn about developing large programs and about theoretical issues). Second, many students in science and engineering have somehow been exempted from being exposed to basic precepts of computer science and algorithmics (instead, they learn a few specific programming tools). In both cases, students are being shortchanged.

This talk is a progress report on nearly four decades of work towards bringing the study of algorithms into the mainstream, with diversions into computer science education, research on analytic combinatorics, and speculation on the future of publishing, all with significant implications for algorithms research. First, applications from all fields of science and engineering now provide direct motivation for the study of algorithms, and a host of fascinating problems that students can address by implementing algorithms on their own computers. Second, analytic combinatorics now gives universal laws of sweeping generality that provide the key insights needed to understand algorithm performance from a scientific viewpoint. Third, the web now enables researchers to easily share problems, data, and algorithm implementations. Applying and developing effective algorithms is now the path of choice to address a broad variety of complex problems that face modern researchers in all fields—our task is to provide them both with an appreciation for algorithm design as an intellectual endeavor and with the algorithms that they need.

The bottom line is that integrating the study of algorithms into the education of every student (and thus making modern scientists and engineers as comfortable with computational models as with mathematical models) is now much easier than it might seem. The growing number of people who can take advantage of this knowledge hold the key to the future.

Venues

2011 ANALCO, San Francisco, CA
2012 Drexel University, Philadelphia, PA

Left-Leaning Red-Black Trees

Abstract

The red-black tree model for implementing balanced search trees, introduced by Guibas and Sedgewick in 1978, is now found throughout our computational infrastructure. Red-black trees are the underlying data structure in the symbol-table implementation in C++, Java, Python, BSD Unix, and many other modern systems. However, current implementations have sacrificed some of the original design goals, so a new look is worthwhile. In this talk, we describe a new variant of red-black trees that leads to substantially simpler code—less than one-fourth as much code as in implementations in common use. Can we analyze average-case performance for this new, simpler version?

Venues

2008 AofA’08, Maresias, Brazil
2008 University of Pennsylvania, Philadelphia, PA
2008 Dagstuhl, Wadern, Germany
2009 LAGOS Symposium, Gramado, Brazil

Creating “Algorithms”

Abstract

This talk describes an ongoing 25-year effort to develop a series of books that describe fundamental algorithms to a broad audience.

The books’ content provides a special opportunity to use technology to more effectively present the material, so the talk focuses on various approaches to take advantage of this opportunity. Particular attention is given to the process of integrating into a single document representations of algorithms (as programs in several languages), text describing them, and high-resolution images representing their underlying data structures.

The perspective taken is historical, anecdotal, and technical, with an eye towards what the experience can tell us about future tools.

Venues

1985 Bell Laboratories, Murray Hill, NJ
1986 RCA David Sarnoff Laboratories, Princeton, NJ
1986 Princeton ACM-IEEE, Princeton, NJ
1990 University of Virginia, Charlottesville, VA
1993 Stanford University, Palo Alto, CA
1994 IDA Systems Research Center, Bowie, MD
2002 Adobe Systems, San Jose, CA

+ 8 old talks

Impatiemment Attendu

2008 Philippe Flajolet 60th birthday, Paris, France

Finding Paths in Graphs

2007 Adobe Systems India, Bangalore, India
2005 Conference on Analysis of Algorithms, Barcelona, Spain
2004 Data Structures Workshop, Dagstuhl, Wadern, Germany
2004 Carleton University, Ottawa, Canada

Quicksort is Optimal

2002 KnuthFest, Stanford University, Stanford, CA

Permutation Generation Methods

2002 Data Structures Workshop, Dagstuhl, Wadern, Germany

New Research on the Theory and Practice of Sorting

1999 Workshop on Analysis of Algorithms, Barcelona, Spain
1999 Ecole Polytechnique, Paris, France
2000 New York Academy of Sciences, New York, NY
2000 Data Structures Workshop, Dagstuhl, Wadern, Germany
2001 Université du Quebec a Montreal, Montreal, Canada

Visualizing the Analysis of Algorithms

1998 Workshop on Analysis of Algorithms, Princeton, NJ

Open Problems in Sorting and Searching

1996 Analysis of Algorithms Workshop, Dagstuhl, Wadern, Germany
1997 Workshop on Probabilistic Algorithms, Princeton, NJ
1998 Data Structures Workshop, Dagstuhl, Wadern, Germany

Shellsort and the Frobenius Problem

1981 Institute for Defense Analyses, Princeton, NJ
1982 INRIA, Rocquencourt, France
1983 Université de Paris-VI, Paris, France
1984 RPI (Class of 1925 Lecture), Troy, NY
1986 City Graduate College, New York, NY
1987 University of Helsinki, Helsinki, Finland
1996 European Symposium on Algorithms, Barcelona, Spain