In traditional “search problems”, an agent aims at exploring a graph in order to find a hidden object as fast as possible. We consider here the Bayesian repeated scenario with several iid instance of the same basic search problem. The objective is, within a given amount of time, to find as many objects as possible with the possibility to leave an instance for the next one at any moment.

We also consider the non-bayesian case with a variant of regret minimization. We provide and analyze several algorithms with fast rates of convergence and/or guaranteed efficiency.

For the game of cops and robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O( n^(k+1) ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. We answer the question of Bonato and Nowakowski on the negative, proving that the O(n^(k+1) ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

This special session will introduce two new PhD students who will each be giving a short talk. Here are the titles and abstracts of the talks:

Combinatorial maps : algebraic and bijective enumeration

Combinatorial maps (which are embeddings of graphs on surfaces) are well studied objects in combinatorics, which have applications in other domains, such as quantum gravity. The goal is to enumerate them (sometimes exactly, sometimes asymptotically). For this purpose, one can resort to (among other things) bijective or algebraic methods. The algebraic method is often more powerful and yields results more easily, however bijections give a more in-depth understanding of the models. Often, formulas are found via powerful methods, then people try to re-prove them bijectively. In this talk, I present what I’m focusing on, on the bijective side (Carell-Chappy formula) and on the algebraic side (KP equations). If time permits, I will explain a simple bijection I discovered during my Master’s internship.

Gradual Set-Theoretic Types

A static type system can be an extremely powerful tool for a programmer, providing early error detection, and offering strong compile-time guarantees on the behavior of a program. However, compared to dynamic typing, static typing often comes at the expense of development speed and flexibility, as statically- typed code might be more difficult to adapt to changing requirements. Gradual typing is a recent and promising approach that tries to get the best of both worlds, by allowing the programmer to finely tune the distribution of dynamic and static checking over a program. However, this “gradualization” is sometimes too coarse, and an expression is often either fully dynamic or fully static. We argue that adding full-fledged union and intersection types (a.k.a. set-theoretic types) to a gradual type system solves this issue by making the transition between dynamic typing and static typing smoother.

La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années. Nous présenterons ici un survol des liens bijectifs avec des familles de cartes planaires, en particulier avec les triangulations (pour les intervalles classiques) et avec les cartes biparties (pour les intervalles dits “nouveaux”), en mettant l'accent sur des symétries de distribution de paramètres que ces bijections révèlent (la partie sur les intervalles nouveaux est basée sur des discussions récentes avec Frédéric Chapoton).

We present randomized algorithms with a total update time of O(m \sqrt{n} log n) for the problems of decremental single-source reachability and decremental strongly connected components on directed graphs. This improves sharply recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler. In this talk, we first review the Las Vegas algorithm by Roditty and Zwick [SICOMP 08] and the deterministic algorithm by Łącki [TALG 13], both with a total update time O(mn) (expected time in the case of the algorithm by Roditty and Zwick). Our algorithms carefully combine these two results, along with new structural properties, including a separation lemma in the case of graphs with a large diameter.

Joint work with Shiri Chechik, Thomas Dueholm Hansen, Jakub Łącki and Nikos Parotsidis.