Gergely Odor

Gergely Ódor

PhD student

EPFL, INDY Lab

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

​

I am advised by Patrick Thiran, and my thesis is on source identification.

​

For English speakers, I go by Greg.

For Hungarian speakers, I go by Gergő.

  • free-mail-icon-142-thumb
  • 2048px-Google_Scholar_logo.svg
  • 2048px-Octicons-mark-github.svg
Download CV

About

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]. 

 
 

Research

ACCEPTED PAPERS

[1] Gergely Ódor, Domonkos Czifra, Júlia Komjáthy, László Lovász, Márton Karsai

Switchover phenomenon induced by epidemic seeding on geometric networks

Proceedings of the National Academy of Sciences Oct 2021, 118 (41) e2112607118

One sentence abstract: We observe empirically and prove theoretically a new phenomenon related to how the initial seeding affects the outcome of an epidemic.

[DOI] [arxiv] [code] [demo]

switchover seeding Hungary
 
 

[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]

illustration_edited.png
illustration_edited.png
 

[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]

ex+tree_edited.png
 

[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]

exponential clocks for fringe trees

SUBMITTED PAPERS

[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]

Screenshot 2021-12-30 at 6.56_edited.png
 
 

[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]

3d grid with extra edge
3d grid with extra edge

PRE-PHD PAPERS

Presentations

  • 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)

 
 

Education

2017 – current
2016 – 2017
2012 – 2016

PhD student at EPFL

Advisor: Patrick Thiran

Master's student at CEU

Advisor: Bálint Virág

Undergraduate student at MIT

Major: Mathematics with Computer Science (18C)

Teaching

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

    • ​Jana Vuckovic

    • Miguel-Angel Sanchez Ndoye

    • Stanislas Jouven

    • Victor Lecomte

    • Satvik Mashkaria

    • 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

 

Acting and hobbies

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

​

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

okulare project
Time and the Conways EPFL
witchhunt