In recent works, Avena and Gaudilliere proposed a randomized flexible method to identify sets of k "central" nodes in a network based on so-called Kirchhoff's forest: a spanning rooted forest measure which generalizes the well-known uniform spanning tree. We recall the main mathematical results behind this method which we then apply in the context of "multiple-node immunization" for complex networks under attack of a viral agent. The latter is a hot topic in network science and it consists in identifying and removing a set of nodes of a given size in a graph to maximally impede the virus spread. Several approaches have been proposed in the literature in relation to numerical and theoretical insights on how classical models for virus spread (so-called compartmental models) evolve on graphs. Based on the stability analysis of these compartmental models, the maximal eigenvalue of the adjacency matrix of the graph has been proposed as a measure for how much resilient the network is. Thus, one of the most common approaches for immunization consists in identifying the set of nodes of a given cardinality, for which the reduced network (obtained by removing these nodes and their incident edges) has smallest maximal eigenvalue. This optimization problem turns out to be a computationally hard problem in the well-known NP-class and the available exact or proxy algorithms offer good solutions and performances only under certain conditions. As we will argue both theoretically and via experimental results on classical synthetic and real-world benchmarks, by using the random k-central nodes associated to the Kirchhoff's forest, one can build a valuable efficient method to improve the state of the art within this multiple-node immunization problem.
Joint work with Michael Emmerich, Alex Gaudilliere and Irina Gurewitsch.

When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determines whether such tasks can be performed with certain levels of accuracy. With the growing size of datasets however, it is crucial not only that the underlying statistical task is possible, but also that is doable by means of efficient algorithms. In this talk we will discuss methods aiming to establish limits of when statistical tasks are possible with computationally efficient methods or when there is a fundamental "Statistical-to-Computational gap" in which an inference task is statistically possible but inherently computationally hard. We will describe recent rigorous correspondences between two different approaches to argue computational hardness of high dimensional inference, the low degree method and methods based on free energy potentials. Based on joint work with Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik.

We study expansion and flooding in evolving graphs, when nodes and edges are continuously created and removed. We consider a model with Poisson node inter-arrival and exponential node survival times. Upon joining the network, a node connects to d = O(1) random nodes, while an edge disappears whenever one of its endpoints leaves the network. For this model, we show that, although at any point in time the graph has a constant (depending on d) fraction of isolated nodes with large, constant probability, flooding still informs a fraction 1-\exp(-Omega(d)) of the nodes in time O(log n). Moreover, at any given time, the graph exhibits a "large-set expansion" property. We further consider a model in which each edge leaving the network is replaced by a fresh, random one. For this second model, we prove that, with high probability i) flooding informs all nodes in time O(log n) and ii) the graph is a vertex expander.

We study the evolution of the graph distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with power-law exponent τ∈(2,3), sample two vertices u_t, v_t uniformly at random when the graph has t vertices, and study the evolution of the graph distance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in t′≥t, called the distance evolution. We show that there is a tight strip around a deterministic function that the distance evolution never leaves with high probability as t tends to infinity. Joint work with Joost Jorritsma.

We define a notion of non-backtracking operator for general weighted graphs, including graphs with negative weights, and prove a Ihara-Bass formula for it. Previously these notions were known only for unweighted graphs.
We use this theory to prove new results on strong refutations of random instances of 3SAT and of other constraint satisfaction problems with an odd number of variables per constraint.