Flajolet Lecture Prize

Last updated

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.

Contents

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 yearLecture yearRecipientPictureLecture titleConferenceLecture location
20132014 Don Knuth KnuthAtOpenContentAlliance.jpg Problems That Philippe Would Have Loved [2] 2014 AofA Conference [15] [16] [17] [18] Paris, France
20152016 Bob Sedgewick Robertsedgewick.jpg Cardinality Estimation [19] 2016 AofA Conference [20] [21] Krakow, Poland
20172018 Luc Devroye Luc Devroye.jpg OMG: GW, CLT, CRT and CFTP [22] 2018 AofA Conference [23] [24] [25] Uppsala, Sweden
20192022 [lower-alpha 1] Wojtek Szpankowski Random Structures in the Brain 047.jpg Analytic Information and Learning Theory: From Compression to Learning2022 AofA Conference [26] Philadelphia, PA, USA
20212022 Svante Janson Svante-Jansson-portrait.jpg The Sum of Powers of Subtrees Sizes for Random Trees2022 AofA ConferencePhiladelphia, PA, USA
20232024 Michael Drmota Michael Drmota.jpg The Moment Method Revisited2024 AofA Conference [27] Bath, UK

See also

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.

Related Research Articles

<span class="mw-page-title-main">Donald Knuth</span> American computer scientist and mathematician (born 1938)

Donald Ervin Knuth is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer science. Knuth has been called the "father of the analysis of algorithms".

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

<span class="mw-page-title-main">Tree (graph theory)</span> Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

<span class="mw-page-title-main">Robert Sedgewick (computer scientist)</span> American computer scientist

Robert Sedgewick is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University and was a member of the board of directors of Adobe Systems (1990–2016). He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA. His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing college curriculums in computer science.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

<span class="mw-page-title-main">Philippe Flajolet</span> French computer scientist

Philippe Flajolet was a French computer scientist.

In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.

<span class="mw-page-title-main">Herbert Wilf</span> American mathematician

Herbert Saul Wilf was an American mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He wrote numerous books and research papers. Together with Neil Calkin he founded The Electronic Journal of Combinatorics in 1994 and was its editor-in-chief until 2001.

In mathematics, the Nørlund–Rice integral, sometimes called Rice's method, relates the nth forward difference of a function to a line integral on the complex plane. It commonly appears in the theory of finite differences and has also been applied in computer science and graph theory to estimate binary tree lengths. It is named in honour of Niels Erik Nørlund and Stephen O. Rice. Nørlund's contribution was to define the integral; Rice's contribution was to demonstrate its utility by applying saddle-point techniques to its evaluation.

<span class="mw-page-title-main">Noga Alon</span> Israeli mathematician

Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.

<span class="mw-page-title-main">Ravindran Kannan</span>

Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.

<span class="mw-page-title-main">Paul Zimmermann (mathematician)</span> French mathematician

Paul Zimmermann is a French computational mathematician, working at INRIA.

Backhouse's constant is a mathematical constant named after Nigel Backhouse. Its value is approximately 1.456 074 948.

<span class="mw-page-title-main">Svante Janson</span> Swedish mathematician

Carl Svante Janson is a Swedish mathematician. A member of the Royal Swedish Academy of Sciences since 1994, Janson has been the chaired professor of mathematics at Uppsala University since 1987.

<span class="mw-page-title-main">Polyknight</span> Figure formed by knights moves on a grid

A polyknight is a plane geometric figure formed by selecting cells in a square lattice that could represent the path of a chess knight in which doubling back is allowed. It is a polyform with square cells which are not necessarily connected, comparable to the polyking. Alternatively, it can be interpreted as a connected subset of the vertices of a knight's graph, a graph formed by connecting pairs of lattice squares that are a knight's move apart.

In computer science, the count-distinct problem (also known in applied mathematics as the cardinality estimation problem) is the problem of finding the number of distinct elements in a data stream with repeated elements. This is a well-known problem with numerous applications. The elements might represent IP addresses of packets passing through a router, unique visitors to a web site, elements in a large database, motifs in a DNA sequence, or elements of RFID/sensor networks.

The Flajolet–Martin algorithm is an algorithm for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic in the maximal number of possible distinct elements in the stream. The algorithm was introduced by Philippe Flajolet and G. Nigel Martin in their 1984 article "Probabilistic Counting Algorithms for Data Base Applications". Later it has been refined in "LogLog counting of large cardinalities" by Marianne Durand and Philippe Flajolet, and "HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet et al.

Analytic Combinatorics is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Robert Sedgewick, and published by the Cambridge University Press in 2009. It won the Leroy P. Steele Prize in 2019.

AofA, the International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms is an academic meeting that has been held regularly since 1993 in the field of computer science, focusing on mathematical methods from analytic combinatorics and probability for the study of properties of algorithms and large combinatorial structures. In early years, different formal names were used, but the meeting and associated community of researchers has always been known as AofA.

Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions.

References

  1. 1 2 "Analysis of Algorithms" . Retrieved 20 March 2021.
  2. 1 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.