Résumé : Tuesday, February 4th
1.30pm: Geoffroy Caillat-Grenier (LIRMM)
From combinatorics of graphs to communication complexity in algorithmic information theory
2.30pm: Alexander Shen (LIRMM)
Erdős, Miller and a simple combinatorial game
3.30pm: discussions & coffee break (room A201)
4.30pm: Thomas Seiller (LIPN)
Games and hierarchy for time-bounded Kolmogorov Complexity
—
Wednesday, February 5th
9.30am: "breakfast" (room A201)
10am: Ivan Titov (LaBRI)
Schnorr randomness
11am: Subin Pulari (LaBRI)
One-way functions and polynomial-time dimension
12pm: Andrei Romashchenko (LIRMM)
High probability means brief description: time bounded versions of the optimal coding theorem
—
Some abstracts
Geoffroy Caillat-Grenier (LIRMM)
From combinatorics of graphs to communication complexity in algorithmic information theory
Abstract: 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 will study some spectral and combinatorial properties of bipartite graphs explicitly constructed.
Those graphs can represent the inputs for a communication problem. Spectral and combinatorial properties of these objects imply information inequalities that make impossible some communication protocols for secret key agreement. For instance, if the graph representing the inputs of the secret key agreement is a spectral expander, we get the worst case in terms of communication complexity. Moreover, the communication protocol is inherently uneven: for two participants, only one of them needs to send all the needed information. Theses facts are connected to the mutual information unextractability phenomenon.
—
Alexander Shen (LIRMM)
Erdős, Miller and a simple combinatorial game
Abstract: Erdős asked whether for every sparse set of positive integers there is a real that is difficult to approximate using denominators from this set. It turns out that this question can be reformulated in terms of a simple combinatorial game and a winning strategy in this game. The strategy can be constructed directly or (with better bound) using Joe Miller's argument about forbidden words and subshifts.
—
Subin Pulari (LaBRI)
One-way functions and polynomial-time dimension
Abstract: Polynomial-time dimension (denoted cdimp) quantifies the density of information of infinite sequences using polynomial time betting algorithms called s-gales. An alternate quantification of the notion of polynomial time density of information is using polynomial-time Kolmogorov complexity rate (denoted
Kpoly.
The corresponding unbounded notions, namely, the constructive dimension and unbounded Kolmogorov complexity rates are equal for every sequence. Analogous notions are equal even at finite-state level. In view of this, it is reasonable to conjecture that cdimp and Kpoly are identical notions.
In this work we demonstrate that cdimp and Kpoly are distinct measures of information density if and only if one-way functions exist. Hence, we provide a new information theoretic characterization of the existence of one-way functions.
As an application of our main result, we demonstrate that if one-way functions exist, then there are individual sequences X whose poly-time dimension strictly exceeds Kpoly(X), that is cdimP(X) > Kpoly(X). We prove analogous results for polytime strong dimension. Further, we show that the gap between these quantities can be made as large as possible (i.e. close to 1). These results provide a strong negative answer to an open question posed by Hitchcock, Vinodchandran and Stull under the assumption that one-way functions exist.
| Dernière modification : Tuesday 28 January 2025 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |