TBA
Les lundis, à partir de 14h - UPEC CMC - Salle P2-131
25 mars 2024
Bornes inférieures et impossibilité en algorithmique distribuée auto-stabilisante
L’auto-stabilisation est un paradigme adapté aux systèmes distribués, particulièrement susceptibles de subir des fautes transitoires. Ces fautes peuvent être des erreurs de corruption de mémoire, de messages, la rupture d’un lien de communication, et peuvent plonger le système dans un état incohérent. Un protocole est auto-stabilisant si, quel que soit l’état initial du système, il garantit un retour à un fonctionnement normal en temps fini.
Avec le développement de réseaux d’objets connectés, censés être autonomes, la question de la conception d’algorithmes tolérants aux pannes ayant un faible coût en termes de consommation énergétique devient cruciale. Une des manières d’appréhender ces problèmes est de chercher à réduire la taille des messages échangés entre les différents nœuds du réseau.
Nous présenterons des résultats négatifs, d’impossibilité et de bornes inférieures pour une famille de problèmes de l’algorithmique distribuée.
25 mars 2024
On the Computability of Compact Sets
The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres, closed manifolds and finite graphs without endpoints : if a set X is homeomorphic to a sphere, a closed manifold or a such graph, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović and others in the recent years. We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs.
18 mars 2024
Mathematical informatics
What is a model of computation? What is a program, an algorithm? While theoretical computer science has been founded on computability theory, the latter does not answer these questions. Indeed, it is a mathematical theory of computable functions, and does not account for computation itself. A symptomatic consequence is the notion of Turing-completeness. This standard (sole?) equivalence between models of computation is purely extensional: it does only care about what is computed and not how, blind to complexity aspects and the question of algorithmic completeness. More importantly, the theory of computation is continuously growing further from how actual machines compute.
I will present a proposal for alternative foundations more faithful to computer science practice and interests. This mathematisation of computer science is grounded within the theory of dynamical systems, focussing on *how* computation is performed rather than only on *what* is computed. I will argue that it generalises computability theory while still allowing to recover standard results.
• provide a uniform account of several lower bounds from algebraic complexity and strengthen them
• define static analysis methods which can be implemented in usable tools
• define families of linear realisability models (realisability models for linear logic)
• lead to a semantic approach of implicit computational complexity
• propose a formal definition of the notion of algorithm
18 mars 2024
Languages of Higher Dimensional Timed Automata
11 mars 2024
Lambda-Calculus, Taylor Expansion and (Tropical) Quantitative Semantics: an overview
4 mars 2024
Computability of extender sets in multidimensional subshifts
Un résultat classique dans l’étude des langages formels est le théorème de Myhill-Nerode, qui donne des conditions nécessaires et suffisantes en terme de langages résiduels pour qu’un langage soit régulier. Dans cet exposé, on essaiera de montrer comment cet outil a été adapté à l’étude des espaces de pavages, où les configurations ne sont plus des mots finis mais des coloriages multidimensionnels infinis. En particulier, on étudiera l’/entropie d’extension/, introduite par R.Pavlov et T.French, qui représente le taux de croissance de cet équivalent aux langages résiduels. On donnera plusieurs caractérisations obtenus sur cette entropie grâce à la théorie de la calculabitlité, sur plusieurs clases de pavages mono- et multidimensionnels.
26 février 2024
Ingredients for a BSP library
The Bulk Synchronous Parallel (BSP) model is a cost model for parallel computation, which algorithm designers can use to estimate how much time their parallel algorithm will take when using multiple processors on their computer simultaneously. Indirectly, it therefore aids also in design of parallel algorithms. The implementation of such a BSP algorithms may be much more complicated, however, because strange interactions inside middle-ware and hardware may unexpectedly ruin the carefully proven complexity bounds. For that reason, various BSP libraries have been proposed and developed, which programmers can use to implement BSP algorithms. This talk presents some of the techniques that such BSP libraries employ in order to present an ordinary computer as a highly reliable and efficient BSP computer.
5 février 2024
Performance Paradox for Matching models with greedy disciplines
A matching model is a triple based on a compatibility graph, a set of Poisson processes and a matching discipline. Each node of the graph is associated with a type of objects and the compatibility graph shows which objects interact. The interaction is the immediate deletion of some objects. If an arriving objet does not interact, it enters the system and wait until it can interact with someone. One of the possible applications of matching models is the kidney exchange system organized in many countries. In this talk I will show a performance paradox: adding more flexibility in the compatibility graph (i.e. adding new edges) will, for some graphs and arrival rates, lead to an increase of the total average sojourn time in the system. And this is proved for any greedy disciplines. We show this property holds for some family of graphs and is lifted for some modular constructions of graphs. As this result is mostly based on strong aggregation of Markov chains, I will begin by a short introduction of this property which is used in general to decrease the size of the models.
29 janvier 2024
Analog characterization of complexity classes
The purpose of this talk is to characterize complexity classes from standard computational complexity theory using systems of ordinary differential equations. We start by recalling concepts related to the general research field of analog computing, from a physical, theoretical, and abstraction level. We then proceed to provide historical context to the main model of the talk, the GPAC from C. Shannon, which describes the behavior of the analog machine called differential analyser. We then explain the evolution that the model had in literature throughout the years and present the details about the analog characterization for the classes P and FP, which connects the GPAC model with the discrete model of Turing machines. We explain how this equivalence should be intended and what are its main consequences. Finally, we briefly discuss some of the more recent developments on the subject, mentioning how to extend the characterization for the class FEXPTIME, for each level of the Grzegorczyk hierarchy, and for polynomial space complexity classes such as FPSPACE and PSPACE.