Compositional Average-Case Timing.

We focus in this talk on a very basic question: how can one derive the average-case time of the sequential composition of two programs from the average-case time of these programs? The answer to this question is crucial to enable static average-case timing. Yet it is not answered in current textbooks. The problem with resolving this question is that it requires the tracking of the distributions of the data. This is currently not feasible.

We show how distribution tracking can be achieved based on a redesign of standard data structuring operations. We outline the theory of Random Bags which formalizes the distributions of the data states. Random Bag Preservation of the operations guarantees the capacity to track the distributions throughout the computations.

This approach has enabled the specification of the novel programming language MOQA (MOdular Quantitative Analysis), implemented in Java 5.0, and its associated timing tool DISTRI-TRACK.

MOQA, essentially a suite of data structure operations for modular design, is guaranteed to be compositional w.r.t. the average-case time measure. This is not the case for general purpose programming languages and in particular for current languages geared towards automated average-case analysis.

The approach links several, thus far largely separate, areas together, including Semantics, Complexity, Analysis of Algorithms and Real-Time Language design. The corresponding unified foundation for algorithmic analysis has led to the solution of bottle-neck problems in automated average-case timing (open problems on dynamic algorithms such as heapsort and deletions and insertions in binary search trees) and has given rise to novel algorithms. In this talk we focus on the analysis of the exact average-case time of heapsort as an application of the new approach.

The talk focuses on the intuitions underlying the approach and should be accessible to anyone with a standard undergraduate background in the Analysis of Algorithms. The talk touches on some core issues which will be discussed in the book ``A Modular Calculus for the Average Cost of Data Structuring'', to appear with Springer.

(Semi-)automated analysis via MOQA.

We present an overview of the MOQA operations using a demo. This includes the basic MOQA operations. We also focus on important concepts aiding average-case analysis such as series-parallel orders and isolated suborders. Given sufficient time we may cover insertions and deletions in binary search trees and the solution to Knott's paradox.

• Adrien Poteaux, DMI XLIM, Université de Limoges. Calcul du groupe de monodromie d'une courbe algébrique plane. Abstract. Slides.

• Frédéric Jouhet, Université Lyon1. q-analogues de deux problèmes de divisibilité via le lemme de Bailey. Abstract. Slides.
• Frédéric Meunier, Projet ALGO, Inria-Rocquencourt. Algorithme HyperLoglog pour estimer la cardinalité de grands multiensembles. Abstract.

• Samuel Vidal, Université de sciences et technologies de Lille. Sur le dénombrement et la génération exhaustive des cartes triangulaires. Abstract. Slides.
• Gilles Schaeffer, LIX, École Polytechnique. Énumération de cartes de genre g et distances dans les cartes. Sous-titre : De l'intérêt des rond-points pour le parcours en largeur. Abstract.

• Damien Stehlé, CNRS, LIP-ENS Lyon, Projet Arenaire. Amélioration de l'analyse de l'algorithme de Kannan pour résoudre SVP Abstract. Slides.
• Luis M. Pardo, Depto. de Matematicas, Estadistica y Computacion, Universidad de Cantabria, Santander, Spain. Aspects conceptuels dans la résolution du 17ième problème de Smale : complexité, probabilités, équations polynomiales et géométrie intégrale. Abstract. Slides.

February 26, 2007

• Éric Fusy, Projet ALGO, Inria-Rocquencourt. Dessin de triangulations : algorithmes, combinatoire, et analyse Abstract. Slides.
• Alexis Darrasse, Équipe SPIRAl, LIP6. Distribution du Degré dans les Réseaux Apolloniens Aléatoires Abstract. Slides.

December 11, 2006

• Laurent Fousse, Projet Spaces, Inria-Lorraine. Intégration numérique avec erreur bornée en précision arbitraire. Abstract. Slides.
• Guénaël Renault, Équipe Spiral, LIP6 Paris. Exploitation des connaissances sur la géométrie des solutions pour la résolution algébrique : Le cas du calcul du corps de décomposition d'un polynôme. Abstract.

November 27, 2006

• Thomas Hélie, Ircam Centre Georges Pompidou, Paris. Séries de Volterra pour la résolution d'équations aux dérivées partielles : une application pour la simulation temps-réel d'instruments de musique. Abstract. Slides.
• Florent Hivert, INSA, Université de Rouen et Jean-Christophe Novelli, IGM, Université de Marne-la-Vallée. Généralisations multi-variées d'une proprieté d'équidistribution de Foata-Schützenberger. Abstract. Slides.

November 20, 2006

• Éric Schost, London, Ontario, Canada. Using fast matrix multiplication in structured linear algebra. Abstract. Slides
• Antonio Cafure, Universidad de Buenos Aires, Universidad Nacional de General Sarmiento Buenos Aires, Argentine. Rational points on varieties over finite fields. Abstract.

October 23 2006

• Laurent Busé, Projet GALAAD, Inria-Sophia-Antipolis. Sur le calcul des résultants itérés. Abstract.

October 20, 2006

• Robin Pemantle, University of Pennsylvania, Philadelphia, PA, USA. Asymptotics of multivariate generating functions. Abstract.

September 25, 2006

• Philippe Flajolet, Projet Algorithmes. Boltzmann sampling and random generation of combinatorial structures. Abstract.
• Frédéric Meunier, Projet Algorithmes. Sigma-jeux sur la grille Abstract.

June 26, 2006

• Alban Quadrat, Projet Café, Inria Sophia. Utilisation de l'algèbre homologique effective pour factoriser et décomposer les systèmes fonctionnels linéaires. Abstract. Slides.
• Alexandre Sedoglavic, LIFL, Univ. Lille I et Projet Alien, INRIA Futurs. Symétries de Lie étendues et étude qualitative des systèmes d'équations paramétriques. Abstract. Slides.

May 29, 2006

• Pierrick Gaudry, Projet SPACES, LORIA. Comptage de points de courbes elliptiques sur un corps fini de grande caractéristique. Abstract.
• François Morain, LIX, École polytechnique et Projet TANC, INRIA Futurs. Calcul d'isogénie entre courbes elliptiques. Abstract. Slides.

May 15, 2006

• Alin Bostan, Projet Algorithmes. Fast computation of power series solutions of systems of differential equations. Abstract. Slides.
• Jürgen Gerhard, MapleSoft, Waterloo, Canada. Rational Summation and Shiftless Factorization. Abstract.

March 27, 2006

• Jean-Marie Maillard, Laboratoire de Physique Théorique de la Matière Condensée, Jussieu, Paris Intégrales multiples de type Ising, groupe de Galois différentiel explicites d'ODE d'ordre supérieur à 10, des systèmes holonomes aux équations différentielles non-linéaires, et ... très au delà. Abstract.
• Frédéric Chyzak, Projet Algorithmes. Le calcul de multisections d'une série solution d'un opérateur différentiel linéaire. Abstract. Slides.

March 13, 2006

• Samuel Friot, Université du Havre. Introduction à la théorie quantique des champs phénoménologique : Électrodynamique quantique perturbative (pQED) et Chromodynamique quantique à grand nombre de couleurs (Large-Nc QCD). Abstract. Slides.
• David Greynat, Centre de Physique Théorique de Marseille. Introduction à la théorie quantique des champs phénoménologique : Les applications de la représentation de Mellin-Barnes et des sommes harmoniques en théorie des champs. Abstract. Slides.

January 30, 2006

• Philippe Di Francesco, Service de Physique Théorique, CEA Saclay. Modèles contraints de mécanique statistique sur réseaux fixes ou aléatoires : objets durs et pliages. Abstract. Slides.
• Philippe Di Francesco, Service de Physique Théorique, CEA Saclay. Des matrices à signe alternant aux variétés orbitales : l'intégrabilité au travail. Abstract.

January 16, 2006

• Changgui Zhang, Université de Sciences et Technologies de Lille. Asymptotiques de $q$-fonctions et leurs zéros. Abstract.
• Élie Mosaki, Université Lyon 1. Partitions sans petites parts . Abstract.

December 5, 2005

• Yann Ponty, LRI, Orsay. Génération aléatoire de mots de langages algébriques et applications aux ARNs. Abstract.
• Nicolas Broutin, McGill University, Montreal, Canada. The diameter of the Minimal Spanning Tree of the Complete Graph. Abstract.

November 14, 2005

• Carine Pivoteau, LIP6. Génération aléatoire sous modèle de Boltzmann : le cas non étiqueté. Abstract.
• Stefan Gerhold, RISC, University of Linz, Austria. Recurrence Relations and Inequalities.Abstract. Slides.

November 7, 2005

• Éric Schost, LIX, École polytechnique. On the complexity of change of order. Abstract. Slides.
• Régis Dupont, LIX, École polytechnique. Arithmetic-Geometric Means of complex numbers and evaluation of modular functions. Abstract.

October 3, 2005

• Micha Hofri, Projet Algorithmes and WPI Computer Science Department, USA. Analysis of an Algorithm for Approximate Median Selection. Abstract. Slides.
• Philippe Robert, Projet Rap. Asymptotique des arbres aléatoires et théorèmes de renouvellement. Abstract. Slides.

Guidelines for Contributors to the Proceedings

LaTeX style files and guidelines on manuscript preparation can be accessed here.

Talks from Previous Years

We publish every year Seminar Proceedings that contain summaries of the talks. The seminar proceedings for the years 1991-2005 can be accessed here.

   Contact Information