NETWORKS

Organiser: Michel Mandjes (University of Amsterdam)

Daniel Dadush (CWI)

On approximating the covering radius and finding dense lattice subspaces

Kannan & Lovasz (Annals of Math `88) asked whether the covering radius of an n-dimensional Euclidean lattice can be tightly characterized using only volumetric information, namely using only determinants of lattice projections. In a recent breakthrough, Regev and Stephens-Davidowitz (STOC `17) answered this question in the affirmative, showing that the determinant of the “sparsest’’ lattice projection can in fact certify a lower bound on the covering radius that is tight up to polylogarithmic factors in the lattice dimension n. In this work, we first refine this characterization, by showing that using a chain of lattice projections one can in fact certify a lower bound that is tight up to the so-called slicing constant of Voronoi cells, which is conjectured to be O(1). Second, we make this theory algorithmic by providing a single exponential time algorithm based on discrete Gaussian sampling for computing an O(log^{2.5} n)-approximately sparsest lattice projection. For this purpose, we rely heavily upon on the notion of canonical filtration of a lattice, developed by Stuhler in `76 and a reverse Minkowski theorem of Regev and Stephens-Davidowitz. 

Julia Komjathy (TU Eindhoven)

Explosive information diffusion on scale-free spatial random graphs

In the talk we study weighted distances in scale-free spatial network models, so called geometric inhomogeneous random graphs (GIRG).  In this model, each vertex is given an independent weight and location from the unit cube (or torus) in d dimensions, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We assign i.i.d. weights to the edges of the created random graphs and study the weighted distance between two uniformly chosen vertices. The question is, how does the weight of the minimal weight path scale as the number of vertices tends to infinity? This length corresponds to the transmission time of the information between a source vertex and another vertex.

We give an if and only if condition on the edge-weights for the following phenomenon that is often called ‘explosion’: the time it takes to transfer the information does not grow with the size of the graph, but rather converges in distribution. 

This model – despite its simplicity – can explain why for instance trendy videos on the internet can reach a large proportion of the world’s population in a short amount of time.