Analytic Combinatorics

• Analytic Combinatorics: the Bologna-2010 Survey. A three hour mini-course given at the XVI Incontro Italiano di Combinatoria Algebrica, Bologna, June 2010. The slides (180 in toto) are in three batches:
  • Symbolic Methods (Bologna11.pdf),
  • Complex Asymptotics (Bologna2.pdf),
  • Random Structures (Bologna3.pdf).
  (Based on previous version: Luchon'09, a six-hour course given at Luchon, France, January 2009.)
• From the Discrete to the Continuous...and Back. Plenary talk at Foundations of Computational Mathematics (FOCM08), Hong Kong, June 2008.
• Analytic Combinatorics---A Calculus of Discrete Structures.. Preliminary version of invited talk at SODA, New Orleans, January 2007. Version of March 2008, Carleton University, Ottawa.
• Singular Combinatorics. A set of 3 lectures in the School Information and Randomness, Santiago de Chile, December 2006. Also serves as skeleton of the Advanced Course on Analytic and Probabilistic Techniques in Combinatoricsat Centre de Recerca Matemàtica (CRM), Barcelona.
• Analytic Combinatorics and Probabilistic Number Theory, Graz, July 2006: Course on Singularities and Random Combinatorial Structures (a set of 8 lectures). Slides: Part 1, Part 2, Part 3, Part 4, Part 5.
• Singularity Analysis: A Perspective [PDF]. A survey talk given at the 10th Workshop on Analysis of Algorithms, MSRI, Berkeley CA, June 2004. [PS]
• Singular Combinatorics (ICM'02) a 45 minute invited lecture given at the International Congress of Mathematicians at Beijing in August 2002. [PS|PDF].
• Algebraic Analytic Combinatorics. Lecture at The Seventh Seminar on Analysis of Algorithms, July 2001, Tatihou Island (France). An abstract is here. [PS(3.5Mb)|PDF]
• Random Systems in Combinatorics. An informal conceptual-historical presentation of Analytic Combinatorics (Chap. 1-5 and 9); serves as introduction to three 1h30 talks at ICTP, Trieste, August 1999 [uncompressed].
• Analytic Combinatorics--Singular Combinatorics[html]. A general presentation of analytic combinatorics at the Institute for Scientific Interchange Foundation, Torino, October 1998 (Also related talk at IHES, Gif-sur-Yvette 1999).
• The Ubiquitous Gaussian Law in Analytic Combinatorics [ps.gz:408kb] (coathored by H. K. Hwang and M. Soria, and also based on joint work with Sedgewick). For more detailed informations, see the preliminary version of a chapter on limit laws that's part of the future book entitled Analytic Combinatorics by Flajolet and Sedgewick. This was an invited talk at the Random Structures and Algorithms Conference, Poznan, August 1997.

Stream Algorithms

• Algorithmes probabilistes sur de grandes masses de données [in French]. Seminar at College de France, January 25, 2008. (Seminar within Pr Gustave Berry's Chair of Technological Innovation, 2007--2008.) VIDEO (61 minutes, in French) . English version of the slides for Fields Institute--Carleton University Distinguihed Lecture, Ottawa, March 26, 2008.
• How to Count with Randomness? [Comment compter avec le hasard?]. In "Probabiliste par hasard", Paris, Probability Lab, September 2007.
• Probabilistic Counting: from analysis to algorithms to programs Survey/tutorial talk at AofA07.
• Quantitative Algorithmics of Massive Data Sets. PARISTIC Conference, Nancy, November 2006.
• Comptage probabiliste: entre mathematique et informatique/Probabilistic Counting---between Mathematics and Computer Science. Talk for the 20th Anniversary of LIPN, University of Paris-Villetaneuse, NOVEMBER 16, 2006.
  Theory and Practice of Probabilistic Counting Algorithms [PDF]. An invited survey talk at ANALCO'04 in New Orleans, January 10, 2004. [PS.GZ| PS]
  New version [DEC 2004]: Invited talk at ASIAN 2004, Chiang Mai.

Urn Processes, Maps, and Combinatorics

• Analyses of Tree Height. October 2010, Paris Institut Henri Poincaré, Séminaire de Combinatoire énumérative et analytique.
• Counting with AB-BA=1. Talk given at the Journées de combinatoire de Bordeaux, January 2010. (Based on joint work with Pawel Blasiak.)
• Analytic Cominatorics of the Mabinogion and OK-Corral Urns. Talk given at Analysis of Algorithms'08, Maresias, Brazil, April 2008. (Based on joint works with Thierry Huillet and Vincent Puyhaubert.)
• Some Exactly Solvable Models of Urn Process Theory. Invited lecture at the MathInfo Conference, Nancy, September 2006.
• Analytic Urns, based on joint work with Kim Gabarro and Helmut Pekari )Barcelona). Talk given at ALGO Seminar, INRIA, January 20, 2003. (Work in progress.)
• Some Airy Phenomena of Analytic Combinatorics---Cores in maps and other stories". Lectures given --at the Analysis of Algorithms meeting, Krnica Morska, July 2000 and related to a presentation ICALP'2000 in Geneva. Based on joint work with C. Banderier, G. Schaeffer, and M. Soria.

Boltzmann Models and Random Generation

• On Buffon Machines and Numbers. Talk given at the AofA'09 Conference, June 2009. (Based on the eponymous paper by Philippe Flajolet, Maryse Pelletier, and Michèle Soria that is available from my publications page.)
  • Longer version of October 2009 for the Franco-Thai Seminar in Pure and Applied Mathematics, Bangkok, October 2009. [Back up: a bigger PDF in case the previous version wouldn't display properly, e.g., on iPhones.]
• Boltzmann Sampling and Random Generation of Combinatorial Structures. Invited lecture at the GASCOM'06 Conference, Dijon, September 11-15, 2006.

Continued fractions

• Pseudo-factorials, elliptic functions, and continued fractions INRIA Rocquencourt, Algorithms Seminar, December 2009. See Publications page for the study (jointly with Roland Bacher), which is due to appear in the Ramanujan Journal.
• Combinatorial Models and Algebraic Continued Fractions. Invited lecture, Conference on Orthogonal Polynomials, Special Functions and Applications, Leuven, Belgium, July 2009. Beefed up from an earlier version: On the sum on a geometric progression... [Sur la somme d'une progression géométrique...]. Colloquium talk, Mathematics Department, Toulouse, May 2008.
• Variations on the comparison of numbers. Colloquium talk, Mathematics Department, Orleans, September 2007. (Based on joint work with Brigitte Vallée.)
• The Fermat cubic, elliptic functions, continued fractions, and a combinatorial tale. Talk at Number Theory Seminar, Grenoble, February 2007. (Based on joint work with Eric Conrad.)

Analysis of Algorithms, Digital Trees

• Digital Trees and Memoryless Sources: from Arithmetics to Analysis. Talk at AofA10, Wien, June 2010. (Based on the eponymous paper by Flajolet, Roux, and Vallée, available from my publications page.)
• Digital Trees: Analysis and Aplications [Les arbres digitaux de l'informatique --- un survol analytique]. Séminaire de Probabilités, Universities Paris 6 and 7. June 15,2010.
• The Number of Symbol Comparisons in QuickSort and QuickSelect. An introduction to the field, which was to be followed by presentations of Brigitte Vallée and Jim Fill on average-case and distributional analyses, respectively. Presented at the AofA Conference, June 2009. (Based on the eponymous paper by Vallée, Clément, Fill, and Flajolet, available from my publications page.)
• Mellin vu du ciel/Mellin seen from the sky. Survey-tutorial talk at ALEA-2008, Luminy, March 2008.
  Some exercises related to this talk:

  Why do we have more than 200 consecutive nines?

  With mu(n) the Möbius function, is the limit equal to $-2$?

  Prove this identity [PF, 2000] relative to harmonic numbers whose indices are squares(!).

• Analysis of Algorithms---Between Mathematics and Computer Science [PDF]. Colloquium talk at INRIA Sophia Antipolis, January 13, 2003. 2003.
  
• Informatique et Mathématique In French. Lecture given at Journées ASTI'2001 (April 2001), Cité des Sciences, Paris. [PS(2.2Mb)]
• Digital Trees and Some of their Avatars (ALP-2002) a lecture given at the Math and Computer Science Workshop of ALP in Paris. It describes some of the "unreasonable effectiveness" of digital trees (aka "tries") in algorithmics as well as the interplay between design and analysis of algorithms in the cases at hand. [uncompressed PS (9Mb)]. Slides are borrowed freely from my KnuthFest Lecture below.
  From Caltech to Page 131: A Seed that Grew..., A lecture on the original de Bruijn-Knuth analysis of digital tries and some of the research that has stemmed from it given at the KnuthFest, Stanford, January 2002. [uncompressed PS (9Mb)]
  • "Algorithmic and Analytic Aspects of the Digital Tree Process". Plenary talk at the Workshop on Information Theory and Networking, Metsovo, June 1999. (Also related talk at RAND'2)
• The Analysis of Hybrid Trie Structures [html]. These are slides of a presentation at the Ninth ACM-SIAM Symposium on Discrete Algorithms (SODA'98) (San Francisco, January 1998) based on the corresponding paper by Clément, Flajolet, and Vallée.
• Analytic Variations on Quadtrees. (based on joint works with G. Gonnet, C. Puech, M. Robson, M. Hoshi, B. Salvy, L. Laforest, T. Lafforgue, and G. Labelle.) Slides from various talks after 1985.

Hashing

• The Airy distribution in analytic combinatorics [ps.gz:462kb] (coauthored by P. Poblete and A. Viola). This talk was given at the Princeton Meeting on Average-Case Analysis of Algorithms (July 1998).
• On the Analysis of Linear Probing Hashing [ps.gz:501kb] (coauthored by P. Poblete and A. Viola). This corresponds to the following research report. The talk has been given at Caen, INRIA Rocquencourt, and Asnelle (Winter 1997-98).

Videos

• Algorithmes probabilistes sur de grandes masses de données [in French], VIDEO (61 minutes, in French).
• Singularity Analysis: A Perspective. Speaker : Philippe Flajolet. MSRI 2004. Video duration is 1:00. Format is mpeg.
• L'analyse d'algorithmes : entre math&ecaute;matiques et informatique.. Speaker : Philippe Flajolet. Colloquium Jacques Morgenstern, Sophia Antipolis, January 2003. The video is in French; real-video format; duration is 1:00.

To obtain copies of other works or paper copy, please contact me.
Technical comments are also most welcome!

Return to Philippe Flajolet's Home Page

Philippe.Flajolet@inria.fr