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 »