Flajolet Lecture Prize

The Philippe Flajolet Lecture Prize is awarded to for contributions to analytic combinatorics and analysis of algorithms, in the fields of theoretical computer science. This prize is named in memory of Philippe Flajolet.

History

The Flajolet Lecture Prize has been awarded since 2014. The Flajolet Lecture Prize is awarded in odd-numbered years. After being selected for the prize, the recipient delivers the Flajolet Lecture during the following year. This lecture is organized as a keynote address at the International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA).^[1] AofA is the international conference that began as a series of seminars, started by Flajolet and others in 1993. The Selection Committee consists of three members from this field.

Scientific topics

The recipients of the Flajolet Lecture Prize work in a variety of areas, including analysis of algorithms, analytic combinatorics, combinatorics, communication protocols, complex analysis, computational biology, data mining, databases, graphs, information theory, limit distributions, maps, trees, probability, statistical physics.

In the inaugural lecture, Don Knuth discussed five "Problems That Philippe Would Have Loved".^[2] Knuth surveyed five problems, including enumeration of polyominoes, mathematical tiling, tree pruning, lattice paths, and perturbation theory. In particular, he discussed the asymptotic enumeration of polyominoes (see OEIS entry A001168^[3] for context and history). Knuth's discussion of forest pruning caused Peter Luschny to observe a connection to Dyck paths (see OEIS entry A091866^[4]). The portion of the talk on Lattice Paths of Slope 2/5 focused on a theorem by Nakamigawa and Tokushige.^[5][6] Knuth made a conjecture about the related enumeration of lattice paths, which was subsequently resolved by Cyril Banderier and Michael Wallner.^[7][8][9] Knuth's discussion of lattice paths also led to the creation of two new OEIS entries, A322632^[10] and A322633.^[11]

The 2016 lecture by Robert Sedgewick focused on a topic dating back to one of Flajolet's earliest papers, on approximate counting methods for streaming data. The talk drew connections between "practical computing" and theoretical computer science. As a key example of these connections, Sedgewick emphasized the way that Flajolet revisited the topic of approximate counting repeatedly during his career, starting with the Flajolet–Martin algorithm for probabilistic counting^[12] and leading the introduction of methods for Loglog Counting^[13] and HyperLogLog counting.^[14] Sedgewick's talk emphasized not only the underlying theory but also the experimental validation of approximate counting, and its modern applications in cloud computing. He also introduced an algorithm called HyperBitBit, which is appropriate in applications which involve small-scale, frequent calculations.

Recipients

Recipients of the Flajolet Lecture Prize^[1]

Selection year	Lecture year	Recipient	Picture	Lecture title	Conference	Lecture location
2013	2014	Don Knuth		Problems That Philippe Would Have Loved[2]	2014 AofA Conference[15][16][17][18]	Paris, France
2015	2016	Bob Sedgewick		Cardinality Estimation[19]	2016 AofA Conference[20][21]	Krakow, Poland
2017	2018	Luc Devroye		OMG: GW, CLT, CRT and CFTP[22]	2018 AofA Conference[23][24][25]	Uppsala, Sweden
2019	2022[a]	Wojtek Szpankowski		Analytic Information and Learning Theory: From Compression to Learning	2022 AofA Conference[26]	Philadelphia, PA, USA
2021	2022	Svante Janson		The Sum of Powers of Subtrees Sizes for Random Trees	2022 AofA Conference	Philadelphia, PA, USA
2023	2024	Michael Drmota		The Moment Method Revisited	2024 AofA Conference[27]	Bath, UK

See also

• List of computer science awards

Notes

1. Szpankowski's lecture was originally scheduled for the 2020 AofA Conference, but the timing was delayed until 2022, due to the COVID-19 pandemic.