VIENNOT , Laurent

New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. Modeling such dynamics, and designing algorithms that take it into account, received considerable attention recently. In this note, we discuss a formal generalization of dynamic...

Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. In this paper, we propose and evaluate an...

Hyperbolicity is a graph parameter which indicates how much the shortest-path distance metric of a graph deviates from a tree metric. It is used in various fields such as networking, security, and bioinformatics for the classification of complex networks, the design of routing schemes, and the analysis of graph algorithms. Despite recent...

Implementation in C++ of algorithms for computing the hyperbolicity of graphs.

L'hyperbolicité est un paramètre de graphe mesurant l'écart entre la métrique des distances dans le graphe et celle d'un arbre. Cette propriété peut se calculer en temps $O(n^4)$ et en espace $O(n^2)$. En effet, les principales approches consistent à considérer tous les quadruplets du graphe, ou bien se basent sur des produits de matrices, et...

There has recently been an increasing desire to evaluate neural networks locally on computationally-limited devices in order to exploit their recent effectiveness for several applications; such effectiveness has nevertheless come together with a considerable increase in the size of modern neural networks, which constitute a major downside in...

Hyperbolicity is a graph parameter which indicates how much the shortest-path distance metric of a graph deviates from a tree metric. It is used in various fields such as networking, security, and bioinformatics for the classification of complex networks, the design of routing schemes, and the analysis of graph algorithms. Despite recent...

We investigate the problem of making a neural network perform some hidden computation whose result can be easily retrieved from the network output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a company. We further assume that the company has limited access to the user's...

We investigate the problem of making an artificial neural network perform hidden computations whose result can be easily retrieved from the network's output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a third party. The user's input to the network contains sensitive...

The lottery ticket hypothesis states that a randomly-initialized neural network contains a small subnetwork which, when trained in isolation, can compete with the performance of the original network. Recent theoretical works proved an even stronger version: every sufficiently overparameterized (dense) neural network contains a subnetwork that,...

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆+1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the O(∆ 2)-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms...

The average properties of the well-known \emph{Subset Sum Problem} can be studied by the means of its randomised version, where we are given a target value $z$, random variables $X_1, \ldots, X_n$, and an error parameter $\varepsilon > 0$, and we seek a subset of the $X_i$'s whose sum approximates $z$ up to error~$\varepsilon$.In this setup, it...

The average properties of the well-known Subset Sum Problem can be studied by the means of its randomised version, where we are given a target value $z$, random variables $X_1, \ldots, X_n$, and an error parameter $\varepsilon > 0$, and we seek a subset of the $X_i$'s whose sum approximates $z$ up to error $\varepsilon$.In this setup, it has...