MSO can be used not only to accept/reject words, but also to transform words into other words, e.g. the doubling function w $\mapsto$ ww. The traditional model for this is called MSO transductions; the idea is that each position of the output word is interpreted in some position of the input word, and MSO is used to define the order on output positions and their labels. I will explain that an extension, where output positions are interpreted using $k$-tuples of input positions, is (a) is also well behaved; and (b) this is surprising.

In many data-driven applications, the data follows some geometric structure, and the goal is to recover this structure. In many cases, the observed data is noisy and the recovery task is even more challenging. A common assumption is that the data lies on a low dimensional manifold. Estimating a manifold from noisy samples has proven to be a challenging task. Indeed, even after decades of research, there was no (computationally tractable) algorithm that accurately estimates a manifold from noisy samples with a constant level of noise.

In this talk, we will present a method that estimates a manifold and its tangent. Moreover, we establish convergence rates, which are essentially as good as existing convergence rates for function estimation.

This is a joint work with Barak Sober.

In this talk we will look at the different ways to define city boundaries, and the relevance to consider socio-demographic and spatial connectivity in urban systems, in particular if interventions are to be considered.

Data that have an intrinsic network structure are becoming increasingly common in various scientific applications. Compressing such data for storage or transmission is an important problem, especially since networks are increasingly large. From an information theoretic perspective, the limit to compression of a random graph is given by the Shannon entropy of its distribution. A relevant question is how much of the information content of a random graph pertains to its structure (i.e., the unlabelled version of the graph), and how much of it is contained in the labels attached to the structure. Furthermore, in applications in which one is interested only in structural properties of a graph (e.g., node degrees, connectedness, frequency of occurrence of certain motifs), the node labels are irrelevant, such that only the structure of the graph needs to be compressed, leading to a more compact representation. In this talk, I will consider the random geometric graph (RGG), where pairs of nodes are connected based on the distance between them in some latent space. This model captures well important characteristics of biological systems, information networks, social networks, or economic networks. Since determination of the entropy is extremely difficult for this model, I will present upper bounds we obtained for the entropy of the labelled RGG. Then, we will focus on the structural information in the one-dimensional RGG. I will show our latest results in terms of the number of structures in the considered model and bounds on the structural entropy, together with the asymptotic behaviour of the bounds for different regimes of the connection range. Finally, I will also present a simple encoding scheme for one-dimensional RGG structures that asymptotically achieves the obtained upper limit on the structural entropy.

arXiv link: https://arxiv.org/abs/2107.13495

The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining. For example, in network epidemiology, the reciprocal of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic threshold of certain network dynamics. In this work, we develop techniques that identify which nodes have the largest impact on the leading non-backtracking eigenvalue. We do so by studying the behavior of the spectrum of the non-backtracking matrix after a node is removed from the graph, which can be thought of as immunizing a node against the spread of disease. From this analysis we derive a centrality measure which we call X-degree, which is then used to predict which nodes have a large influence in the epidemic threshold. Finally, we discuss work currently in progress on connections with eigenvector localization and percolation theory.