SCIENTIFIC PROGRAMS AND ACTIVITIES

Fields-Carleton Distinguished Lecture Series March 26, 2008 -- 6:00 pm, Carleton University Campus 1125 Colonel By Drive, Ottawa
	Philippe Flajolet INRIA Rocquencourt

General public talk:
Wednesday March 26, 2008 -- 6:00 pm,
103 Steacie Building

Counting with Probabilities

Several algorithms have appeared over the past two decades and have proved instrumental in extracting efficiently quantitative characteristics of very large data sets. The algorithms are by nature probabilistic; they exploit properties of simple discrete models and their design is tightly intertwined with their analysis. Singularly efficient solutions have been found that defy information theoretic lower bounds applicable to deterministic algorithms. Characteristics like the total number of elements, cardinality (the number of distinct elements), frequency moments, as well as unbiased samples can be gathered with little loss of information and only a small probability of failure. The algorithms are applicable to traffic monitoring in networks, to data base query optimization, and to some of the basic tasks of data mining. Their design and optimization involve a variety of methods from discrete mathematics, complex and asymptotic analysis, as well as probability theory.

-----
A second talk for mathematical sciences
Thursday March 27, 2008 -- 2:00 pm
4351 Herzberg Laboratories

Analytic Combinatorics: A Calculus of Discrete Structures
The efficiency of many discrete algorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the geometry of the resulting functions. In this way, an operational calculus of discrete structures emerges. Applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.

---

Philippe (Patrick, Michel) Flajolet (December 1, 1948) is a French computer scientist.

A former student of École Polytechnique, Philippe Flajolet got a Ph.D. in computer science from University Paris VII in 1977 and a doctorate of state in 1979. Most of Philippe Flajolet's research work was dedicated towards generic methods for analyzing the computational complexity of algorithms. He introduced the theory of analytical combinatorics. A summary of his research up to 1998 can be found in the article "Philippe Flajolet's research in Combinatorics and Analysis of Algorithms" by H. Prodinger and W. Szpankowski, Algorithmica 22 (1998), 366-387.
Philippe Flajolet is currently a research director (senior research scientist) at INRIA in Rocquencourt.
From 1994 to 2003 he was a corresponding member of the French Academy of Sciences, and has been a full member from 2003 on. He is also a member of the Academia Europaea and was awarded the Silver Medal of CNRS in 2004.

back to top