Marie Albenque (LIX, École Polytechnique, France): Local limit of random discrete surface with (or without!) a statistical physics model
A planar map is an embedding of a planar graph in the sphere, considered up to deformations. A triangulation is a planar map, where all the faces are triangles. In 2003, in order to define a model of generic planar geometry, Angel and Schramm studied the limit of random triangulations on the sphere. They proved that this model of random maps converges for the Benjamini-Schramm topology or local topology, towards the now famous Uniform Infinite Planar Triangulation (or UIPT), a probability distribution on infinite triangulations. Soon after, Angel studied some properties of the UIPT. He established that the volume of the balls the UIPT of radius R scales as R4. Similar results (but with quite different proofs) were then obtained for quadrangulations by Chassaing and Durhuus and Krikun.
The results cited above deal with models of maps that fall in the same “universality class”, identified in the physics literature as the class of “pure 2D quantum gravity”: the generating series all admit the same critical exponent and the volume of the balls of the local limits of several of those models of random maps are known to grow as R4. To capture this universal behaviour, a good framework is to consider scaling limits of random maps in the Gromov Hausdorff topology. Indeed, for a wide variety of models the scaling limit exists and is the so-called Brownian map.
To escape this pure gravity behaviour, physicists have long ago understood that one should “couple gravity with matter”, that is, consider models of random maps endowed with a statistical physics model. I will present in particular the case of triangulations decorated by an Ising model. It consists in colouring in black and white the vertices of a triangulation, and consider probability distribution which are now biased by their number of monochromatic edges. In a recent work, in collaboration with Laurent Ménard and Gilles Schaeffer, we proved that the local limit of this model also exists.
In this talk, I will present these results and explain the main ideas underlying their proof, which rely in part on some enumerative formulas obtained by Tutte in the 60s, or their generalization to coloured triangulations by Bernardi and Bousquet-Mélou.
Maria-Florina Balcan (Carnegie Mellon University, USA): Generalization Guarantees for Data-driven Mechanism Design
Many mechanisms including pricing mechanisms and auctions typically come with a variety of tunable parameters which impact significantly their desired performance guarantees. Data-driven mechanism design is a powerful approach for designing mechanisms, where these parameters are tuned via machine learning based on data. In this talk I will discuss how techniques from machine learning theory can be adapted and extended to analyze generalization guarantees of data-driven mechanism design.
Amina Doumane (CNRS, LIP, ENS Lyon, France): Regular expressions for graphs of tree-width 2
We propose a syntax of regular expressions, whose languages are graphs of tree width 2. We show that these languages correspond exactly to MSO definable languages of graphs of tree width 2.
Fabian Kuhn (University of Freiburg, Germany): Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring
The problem of obtaining fast deterministic algorithms for distributed symmetry breaking problems in graphs has long been considered one of the most challenging problems in the area of distributed graph algorithms. Consider for example the distributed coloring problem, where a (computer) network is modeled by an arbitrary graph G = (V,E) and the objective is to compute a vertex coloring of G by running a distributed algorithm on the graph G. It is maybe not surprising that randomization can be a helpful tool to efficiently compute such a coloring. In fact, as long as each node v ∈ V can choose among deg(v)+1 different colors, even an almost trivial algorithm in which all nodes keep trying a random available color allows to color all nodes in O(log n) parallel steps. How to obtain a similarly efficient deterministic distributed coloring algorithm is far less obvious. In fact, for a long time, there has been an exponential gap between the time complexities of the best randomized and the best deterministic distributed algorithms for various graph coloring variants and for many other basic graph problems. In the last few years, there however has been substantial progress on deterministic distributed graph algorithms that are nearly as fast as randomized algorithms for the same tasks. In particular, in a recent breakthrough, Rozhoň and Ghaffari managed to reduce the gap between the randomized and deterministic complexities of locally checkable graph problems to at most poly log n.
In the talk, we give a brief overview of the history of the problem of finding fast deterministic algorithms for distributed symmetry breaking problems and of what we know about the relation between deterministic and randomized distributed algorithms for such problems. Together with some additional recent developments, the result of Rozhoň and Ghaffari provides a generic, somewhat brute-force way to efficiently derandomize randomized distributed algorithms. Apart from this, there has also been substantial progress on more direct, problem-specific algorithms. In the talk, we in particular discuss some novel deterministic distributed graph coloring algorithms. The algorithms are significantly faster and we believe also simpler than previous algorithms for the same coloring problems.
Loading...