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[lower-alpha 1]	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.

References

1. "Analysis of Algorithms". Retrieved 20 March 2021.
2. Donald Knuth. "Problems That Philippe Would Have Loved" (PDF). Stanford University. Retrieved 23 March 2022.
3. N. J. A. Sloane. "Number of fixed polyominoes with n cells". On-Line Encyclopedia of Integer Sequences. Retrieved 23 March 2022.
4. Emeric Deutsch. "Number of Dyck paths of semilength n having pyramid weight k". On-Line Encyclopedia of Integer Sequences. Retrieved 23 March 2022.
5. Nakamigawa, Tomoki; Tokushige, Norihide (2012). "Counting Lattice Paths via a New Cycle Lemma". SIAM Journal on Discrete Mathematics. 26 (2). Society for Industrial and Applied Mathematics: 745–754. CiteSeerX 10.1.1.220.6893. doi:10.1137/100796431. Retrieved 23 March 2022.
6. Hugo Pfoertner. "a(n) = 2*binomial(7*n-1,2*n)/(7*n-1)". On-Line Encyclopedia of Integer Sequences. Retrieved 23 March 2022.
7. Banderier, Cyril; Wallner, Michael (2015). "Lattice paths of slope 2/5". 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). pp. 105–113. arXiv:1605.02967. doi:10.1137/1.9781611973761.10. ISBN 978-1-61197-376-1. S2CID 15496496.
8. Banderier, Cyril; Wallner, Michael (2015). "Lattice paths of slope 2/5". Society for Industrial and Applied Mathematics, Meeting on Analytic Algorithmics and Combinatorics. Retrieved 23 March 2022.
9. Banderier, Cyril; Wallner, Michael (2019). "The Kernel Method for Lattice Paths Below a Line of Rational Slope". In Andrews, George; Krattenthaler, Christian; Krinik, Alan (eds.). Lattice Path Combinatorics and Applications. Developments in Mathematics. Vol. 58. Springer. pp. 119–154. doi:10.1007/978-3-030-11102-1. ISBN 978-3-030-11101-4. S2CID 197480284. Retrieved 23 March 2022.
10. Hugo Pfoertner. "Decimal expansion of the real solution to 23*x^5 - 41*x^4 + 10*x^3 - 6*x^2 - x - 1 = 0". On-Line Encyclopedia of Integer Sequences. Retrieved 23 March 2022.
11. Hugo Pfoertner. "Decimal expansion of the real solution to 11571875*x^5 - 5363750*x^4 + 628250*x^3 - 97580*x^2 + 5180*x - 142 = 0, multiplied by 3/7". On-Line Encyclopedia of Integer Sequences. Retrieved 23 March 2022.
12. Flajolet, Philippe; Nigel Martin, G. (1985). "Probabilistic counting algorithms for data base applications" (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8.
13. Durand, Marianne; Flajolet, Philippe (2003). "Loglog Counting of Large Cardinalities" (PDF). Algorithms - ESA 2003. Lecture Notes in Computer Science. Vol. 2832. p. 605. doi:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Retrieved 23 March 2022.
14. Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm". Discrete Mathematics and Theoretical Computer Science Proceedings. AH. Nancy, France: 137–156. Retrieved 23 March 2022.
15. "AofA 2014". Retrieved 20 March 2021.
16. "Conference Proceedings front page for AofA 2014 from HAL multidisciplinary open-access archive at INRIA, France". Retrieved 20 March 2021.
17. "full scientific Conference Proceedings for AofA 2014 from HAL multidisciplinary open-access archive at INRIA, France". Retrieved 20 March 2021.
18. "Don Knuth's Public Lectures in 2014". Retrieved 23 March 2022.
19. Bob Sedgewick (16 October 2020). "Cardinality Estimation".
20. "AofA 2016". Retrieved 20 March 2021.
21. "full scientific Conference Proceedings for AofA 2016 from Jagiellonian University in Kraków" (PDF). Retrieved 20 March 2021.
22. Luc Devroye. "Articles in edited proceedings".
23. "AofA 2018". Archived from the original on 22 August 2019. Retrieved 20 March 2021.
24. "full scientific Conference Proceedings for AofA 2018 from Dagstuhl Research Online Publication Server" (PDF). Retrieved 20 March 2021.
25. "Special Issue of Algorithmica journal dedicated to selected papers from AofA 2018". Retrieved 20 March 2021.
26. "Szpankowski Wins Flajolet Prize". 11 February 2020. Retrieved 20 March 2021.
27. "AofA2024". Retrieved 29 June 2023.

External links

• Analysis of Algorithms international community website