The Philippe Flajolet Lecture Prize is awarded to for contributions to

analytic combinatorics In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet an ...

and

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

, in the fields of

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

. 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). 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

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

communication protocols A communication protocol is a system of rules that allows two or more entities of a communications system to transmit information via any kind of variation of a physical quantity. The protocol defines the rules, syntax, semantics and synchroniza ...

complex analysis Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is helpful in many branches of mathematics, including algebra ...

computational biology Computational biology refers to the use of data analysis, mathematical modeling and computational simulations to understand biological systems and relationships. An intersection of computer science, biology, and big data, the field also has fo ...

, data mining,

databases In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases spa ...

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

, limit distributions,

maps A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes. Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Althoug ...

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...

statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...

. In the inaugural lecture, Don Knuth discussed five "Problems That Philippe Would Have Loved". Knuth surveyed five problems, including enumeration of

polyominoes A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in p ...

mathematical tiling A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of g ...

tree pruning Pruning is a Horticulture, horticultural, Arboriculture, arboricultural, and silviculture, silvicultural practice involving the selective removal of certain parts of a plant, such as branches, buds, or roots. The practice entails the ''targe ...

, lattice paths, and

perturbation theory In mathematics and applied mathematics, perturbation theory comprises methods for finding an approximate solution to a problem, by starting from the exact solution of a related, simpler problem. A critical feature of the technique is a middl ...

. In particular, he discussed the asymptotic enumeration of polyominoes (see

OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...

entry A001168 for context and history). Knuth's discussion of forest pruning caused Peter Luschny to observe a connection to Dyck paths (see

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 An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

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 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 count-distinct ...

for probabilistic counting and leading the introduction of methods for Loglog Counting and

HyperLogLog HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the ''exact'' cardinality of the distinct elements of a multiset requires an amount of memory proportional to th ...

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.

Recipients

Notes

References

{{reflist

External links