SCIENTIFIC PROGRAMS AND ACTIVITIES
|March 12, 2014|
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.
Analytic Combinatorics: A Calculus of Discrete Structures
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.