Flajolet Lecture Prize
- 2 min read
- 3 chapters
Related on Lably
Through Combinatorics, Data mining and Database
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). 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.
Sign in to keep reading
2 more chapters are free with a Lably account.
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". 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 for context and history). Knuth's discussion of forest pruning caused Peter Luschny to observe a connection to Dyck paths (see OEIS entry A091866). The portion of the talk on Lattice Paths of Slope 2/5 focused on a theorem by Nakamigawa and Tokushige. Knuth made a conjecture about the related enumeration of lattice paths, which was subsequently resolved by Cyril Banderier and Michael Wallner. Knuth's discussion of lattice paths also led to the creation of two new OEIS entries, A322632 and A322633.
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 and leading the introduction of methods for Loglog Counting and HyperLogLog counting. 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.