Sergio Cabello - Computational Geometry with Predictions

Algorithms with predictions have received considerable attention in recent years. Given a problem instance and a prediction for the solution, we would like to devise a procedure that solves the problem
in such a way that the algorithm performs “better” when the prediction is “close” to the correct information. “Better” may be, for example, in terms of running time, approximation factor, or competitive ratio. Different measures of “closeness” may be used depending on the problem, or alternatively we may assume that predictions obey some probabilistic models.
I will explain some recent research in computational geometry that follows this paradigm of algorithms with predictions. In particular, we will look at the problem of searching for a target point at some unknown location when we get information about the approximate distance to the target and at the problem of computing the Delaunay triangulation in the plane when we are given a triangulation that is close to be the Delaunay triangulation.
Most of the material will be based on joint work with Timothy M. Chan and Panos Giannopoulos.

Neeldhara Misra - On Fairness with Graphical Valuations

The existence of envy-free up to any item (EFX) allocations is widely regarded as a central open problem in discrete fair division, and remains open beyond three agents. A recent line of work has carved out a structurally rich and surprisingly tractable corner of the landscape: the class of graphical valuations, introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023), in which agents are vertices of a graph, items are edges, and each item is valued only by its two endpoint-agents. Their remarkable observation that EFX always exists on such instances has catalyzed a fast-moving body of follow-up work. This talk will survey this trajectory, leading to various intriguing questions this young area has surfaced. We hope to demonstrate that graphical valuations have become a productive meeting point for structural graph theory, parameterized complexity, and fair division.

• Bus departure at 14h00
• Train for the top at 14h40
• Return train at 17h20
• Departure for the city center at 18h00

Address : 3 place de la Victoire, 63000 Clermont-Ferrand, France

Pierre Fraigniaud - Algorithmic Meta-Theorems for Distributed Computing

Algorithmic meta-theorems can be viewed as theorems applying to large classes of algorithmic problems at once. An archetypal example of algorithmic meta-theorems is Courcelle's theorem (1990), which states that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. Such a theorem is remarkable for many reasons, in particular for it establishes tight connections between sequential algorithms complexity, graph theory, and logic. It is only recently that meta-theorems have been formulated for distributed computing. This talk will survey some of the recent contributions in this field. In particular, it will address distributed decision for graph properties definable in first-order logic in graphs of bounded expansion, and distributed certification for graph properties definable in monadic second-order logic in graphs of bounded treewidth, as well as in graphs of bounded clique-width.