Posts classified under: Séminaire Algo

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 such a graph, then any algorithm that semicomputes X in some … Continue reading Séminaire Algorithmique : Djamel Eddine Amir (LISN, Univ. Paris-Saclay) « Computability of Compact Spaces »

Several connexions between information theory and combinatorics of graphs have been explored in the last decades. Following this path, we use tools from spectral graph theory to show impossibility results in information theoretic cryptography. We place ourselves in the Kolmogorov complexity framework. After a short introduction to algorithmic information theory and secret key agreement, we … Continue reading Séminaire Algorithmique : Geoffroy Caillat-Grenier (LIRMM, Univ. Montpellier), « From combinatorics of graphs to communication complexity in algorithmic information theory »

Hybrid automata form an expressive model to describe systems combining continuous and discrete evolution modes. However, most verification problems are undecidable for this model. We recall the particular case of Timed Automata where the reachability problem is PSPACE-complete. We introduce the class of Interrupt Timed Automata featuring special clocks called stopwatches that can be suspended. … Continue reading Séminaire algorithmique : Béatrice Bérard (LIP6, Sorbonne Univ.), « The reachability problem for Polynomial Interrupt Timed Automata»

Enumerating is the task of generating all solutions associated with an instance of a computational problem. We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In … Continue reading Séminaire Algorithmique : « Enumeration Classes Defined by Circuits », Arnaud Durand (IMJ, Univ. Paris-Diderot)

Balanced binary search trees are a common data structure for implementing ordered sets, with three kinds of queries: checking whether a given value belongs to the set, inserting a value, and deleting a value; the two latter queries require updating the data structure. Some implementations, like red-black trees or weak AVL trees, allow efficient update … Continue reading Séminaire algorithmique : Vincent Jugé (LIGM, Univ. G. Eiffel, Paris Est), « Write-efficient updates for AVL trees »

Coalition formation is a cooperative game theory framework in which a set of agents, required to perform implicit or explicit tasks, must be divided into subgroups (called coalitions), according to collective criteria and a utility function describing the utility of each coalition. This is equivalent to a problem of partitioning the set of agents. The … Continue reading Séminaire Algorithmique : Josselin Guéneron (GREYC) « Repeated Stochastic Coalition Formation: representations and algorithmic approaches »

In 1964, R. Berger proved the existence of strongly aperiodic subshifts of finite type (SFT) on $\mathbb{Z}^2$, and used them to prove the undecidability of the Domino Problem. With the goal of understanding what aspects of $\mathbb{Z}^2$ account for this result, there has been an effort in recent years to characterize the groups with undecidable … Continue reading Séminaire Algorithmique : Nicolas Bitar (LAMFA, Univ. Picardie), « Subshifts of finite type and quasi-isometries beyond groups »

A graph is chordal if it has no induced cycle of length greater than 3. Alternatively, Dirac proved that a graph is chordal if and only if every minimal separator is a clique. From this characterization it is not hard to prove that a k-connected chordal graph can be uniquely decomposed into (k+1)-connected components by … Continue reading Séminaire Algorithmique : « Enumeration of some families of chordal graphs », Jordi Castellvi (Univ. Barcelone, Espagne)

Current distributed source version-control systems (such as Git and Mercurial), track the history of changes using an append-only directed acyclic graph, sometimes complemented by labels subsequently attached to commits. We present a chain-based and a dichotomy-based framework, both leveraging incremental indices, to answer reachability queries in sub-linear time, and efficiently perform label synchronisation between users. … Continue reading Séminaire Algorithmique : « Commit graphs in Version-Control Systems: incremental reachability and label discovery », Euxane Tran-Girard (LIGM, Univ. Paris-Est G. Eiffel)

La notion de structure transparaît dans de nombreux domaines scientifiques comme une approche pragmatique pour capturer le fait que des objets complexes peuvent être décomposés en éléments plus simples. Nous proposons une formalisation de cette notion et montrons comment s'en servir pour unifier diverses variations des diagrammes de décision binaires (BDD, une représentation simple, pragmatique, … Continue reading Séminaire Algorithmique : « Introduction à la théorie des structures et son application aux fonctions Booléennes », Joan Thibault (IRISA, Rennes)

In this talk, we will explore graphs of shortest paths—directed acyclic graphs (DAGs) derived from shortest path traversals of a graph rooted at a fixed source. After establishing a precise definition of these structures, we will examine methods for uniformly sampling them and investigate their typical shape. Along the way, we will uncover interesting connections … Continue reading Séminaire Algorithmique : « Graphs of Shortest Paths », Mehdi Naima (LIP6, Sorbonne Univ.)

The domatic number of a graph G is the maximum number of pairwise disjoint dominating sets of G. We are interested in the LP-relaxation of this parameter, which is called the fractional domatic number of G. We study its extremal value in the class of graphs of minimum degree d. The fractional domatic number of … Continue reading Séminaire Algorithmique : « Fractional domatic number and minimum degree », Hugo Demaret (Ecole Polytechnique et GREYC)