Posts classified under: General

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)