Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Calin: Combinatorics, ALgorithmics, INteractions

The CALIN team brings together researchers with skills in a variety of aspects of combinatorics (analytic, bijective, geometric, and algebraic). They are interested in the complexity of algorithms, with a focus on determining their behaviour on average or in distribution. They also have an interest in the fine-grained analysis of data structures, and study problems of physics with a distinct combinatorial flavour, or apply methods from physics to combinatorial problems. The team is organised into two subgroups: one of them focuses on the analysis of algorithms and combinatorial structures, and the other is devoted to the interactions between combinatorics, geometry and physics.

The research is organised along two main axes.

First Axis : Analysis of algorithms and combinatorial structures

The first axis concerns the Theory of Algorithms, and their rigorous analysis, mainly performed through the statistical understanding of the arising random structures and their asymptotics.  We investigate all of those combinatorial structures that are multivalent and omnipresent in Theoretical Computer Science: words, with their link to monoid, ring and group theory; graphs and trees, appearing e.g. as search trees, or as networks, or transition structures in automata; random walks and other dynamics on such graphs; partitions and permutations... Our methods are bijective, probabilistic, or arising from an analytic approach through generating functions and singularity analysis, along the research line pioneered by Philippe Flajolet.

Second Axis: Combinatorial Physics

A second axis is oriented towards what could be called ``Combinatorial Physics'', i.e. a cross-fertilisation of fields within Theoretical Physics and Theoretical Computer Science (with a problem--method exchange in both directions), of which a master example is the combinatorics of graphs and diagrams, based on Hopf Algebras, fundamental for the rigorous understanting of the Renormalisation procedure in a family of toy models in Quantum Field Theory.  In such
a subject the synergy of the members of the team is crucial, as competences of Algebra (such as Representation Theory or Lie Groups) and some background of theoretical physics are an essential complement to tools more specific to combinatorics, such as Lyndon words or symmetric functions, along the research line pioneered by Marcel-Paul Schützenberger.