SNSF Postdoc Mobility Fellow

hosted by Mátron Karsai at CEU, Vienna

My research interests are at the interface of probability theory, theoretical computer science and network science.

​

My PhD advisor was Patrick Thiran, and my thesis was on source identification.

​

For English speakers, I go by Greg.

For Hungarian speakers, I go by Gergő.

I am interested in problems concerning networks that are challenging either from a mathematical modelling or an algorithmic perspective, or both. My thesis is on the source idenitfication problem, which fortunately qualifies as "both": the goal is to design efficient algorithms that find the first infected individual (also called patient zero) during an epidemic, based on sparse measurements about who got infected and when.

On the algorithmic side, I have worked on rigorously quantifying the role of adaptivity in source identification: the difference between the problem settings when the measurements are chosen adaptively vs non-adaptively. If the epidemic spreads very aggressively, the theoretical analysis ([3] and [4]) becomes equivalent to adaptive and non-adaptive versions of the metric dimension from the combinatorics literature. If the epidemic is less aggressive, then there is more stochasticity in the problem, making the analysis more challenging [2]. Interestingly, in some cases adaptivity only plays a small role [3], whereas in others, its role is very substantial [2].

​

More on the modelling (but still rigorous) side, I have worked on relaxing the assumption in the source identification problem that the underlying contact network is fully known to the algorithm [5]. Also in this direction, we studied the robustness of the metric dimension to single edge changes [6]. Slightly deviating from the algorithmic source identification problem, I have worked on understanding how the location of (multiple) initial seeds affect the outcome of an epidemic [1]. 

​

Click here to access my thesis.

[2] Victor Lecomte, Gergely Ódor, Patrick Thiran

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

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.

[DOI] [arxiv]

[3] Gergely Ódor, Patrick Thiran

Sequential metric dimension for random graphs

Journal of Applied Probability, Volume 58, Issue 4, December 2021, pp. 909 - 951

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.

[DOI] [arxiv] [code]

[4] Júlia Komjáthy, Gergely Ódor

Metric dimension of critical Galton-Watson trees and linear preferential attachment trees

European Journal of Combinatorics 95 (2021), 103317

One sentence abstract: Building on the literature of fringe trees, we prove law of large numbers type results for the metric dimension of various random trees.

[DOI] [arxiv]

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

Source Detection via Contact Tracing in the Presence of Asymptomatic Patients

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. 

[arxiv]

[6] Satvik Mashkaria, Gergely Ódor, Patrick Thiran

On the robustness of the metric dimension of grid graphs to adding a single edge

One sentence abstract: We prove that if we add an extra edge to a (large enough) d-dimensional grid graph, then the resulting graph will have metric dimension between d and 2d, and we almost completely settle the case for d=2.

[arxiv] [code]

• 2022 July: NetSci 2022 @Shanghai (online)
     Title: Switchover phenomenon induced by epidemic seeding on geometric networks (contributed talk)

• 2022 July: Epidemology and modelling workshop (Kecskemét)
     Title: Identifying patient zero and proximity-sensitive awareness (invited speaker)

• 2022 May: Erdös Center Workshop: Mathematics of Large Networks (Budapest)
     Title: Source Identification via Contact Tracing in the Presence of Asymptomatic Patients (contributed talk)

• 2021 November: Budapest Semesters in Mathematics Colloquium (Budapest)
     Title: Switchover phenomenon induced by epidemic seeding on geometric networks (invited speaker)

• 2021 July: Franco-Dutch meeting “Bézout-Eurandom” (IHP Paris/online)
     Title: Switchover phenomenon induced by epidemic seeding on geometric networks

• 2021 July: Rátz László Conference of Mathematics Teachers (online)
     Title: Random trees and epidemic spreading (invited speaker)

• 2020 February: Budapest University of Technology and Economics Stochastic Seminar (TU Budapest)
     Title: Sequential metric dimension for random graphs (invited speaker)

• 2019 July: 19th International Conference on Random Structures and Algorithms (ETH Zurich)
     Title: Sequential metric dimension for random graphs (contributed talk)

• 2019 March: YEP XV "Information Diffusion on Random Networks" (TU Eindhoven)
     Title: Source localization with adaptive sensor selection in random graphs (contributed talk)

• 2018 April: Wiki Workshop at The Web Conference (WWW2018 Lyon)
     Title: How did Wikipedia become navigable (poster)

• 2014, 2015, 2018 December: Statistical Physics Holiday Seminar, Eotvos Lorand University (ELTE)

2017 – 2022

• 2018 – 2021: Supervised semester projects or internships at EPFL for

  • ​Jana Vuckovic

  • Miguel-Angel Sanchez Ndoye

  • Stanislas Jouven

  • Victor Lecomte

  • Satvik Mashkaria

  • Anastasiia Kucherenko

  • Nicolas D'Argenlieu

  • Constantin Isabela

  • Farzad Pourkamali

• ​2020 – 2021: Volunteer tutor (Maths and English) at the Menetszél association for children with disadvantaged backgrounds

• 2017 – 2020: TA for various courses at EPFL and CEU

  • Theory of Computing

  • Dynamical Systems Theory

  • Probability and Statistics

  • Matrix Computations with Applications

• 2014 – 2015: Tutor for various undergraduate courses at MIT

I took several theater courses at MIT and at Metro Works, and ​I performed as an actor in a few plays:

• 2022 Summer: Played Thomas in "Beszélnünk kell" as part of the Hatásszünet group (created by Szilvia Markos and Heléna Ménesi)

• 2021 -- 2022: Read various parts in four different short plays while participating in the Okuláré project​​​​

• 2019 Spring: Played Alan in The Time and the Conways by J.B. Priestley (directed by Suzanne Balharry)

• 2015 Spring: Performed in the Up and Down 24h show (directed by István Cziegler)

• 2014 Fall: Played Judge John Hathorne in The Curcible by Arthur Miller (directed by Caleb Hammond)​​

• 2014 Spring: Played the Intruder in Present Simple by István Cziegler (directed by István Cziegler)

​

Otherwise, I enjoy hiking, taekwondo and playing ultimate frisbee, among many other things.