The power of adaptivity in source identification with time queries on the path Permalink

Victor Lecomte, Gergely Ódor, and Patrick Thiran

Published in Theoretical Computer Science, 2022

One sentence abstract:

We provide the first theoretical results on the query complexity of the source identification problem when queried nodes report their infection time; in the adaptive case we need only Θ(loglog(n)) queries, while in the non-adaptive case Θ(n) queries are needed.

Source Detection via Contact Tracing in the Presence of Asymptomatic Patients Permalink

Gergely Ódor, Jana Vuckovic, Miguel-Angel Sanchez Ndoye, Patrick Thiran

Published in arxiv, 2021

One sentence abstract:

We define and prove rigorous results about a new source identification framework, where the network is initially not known to the algorithm, but must be explored through queries (similarly to the node infection times), and we evaluate our algorithms on realistic datasets.

Sequential metric dimension for random graphs Permalink

Gergely Ódor and Patrick Thiran

Published in Journal of Applied Probability, 2021

One sentence abstract:

We prove that the sequential version of the metric dimension (where the landmarks can be chosen adaptively to distinguish every pair of nodes based on distances) is only a multiplicative constant factor smaller than the (non-adaptive) metric dimension in Erdos-Renyi graphs