---
res:
  bibo_abstract:
  - "In this thesis, we took a look at networks, and more specifically, at networks
    that change over time, whether those are networks in the distributed algorithms
    sense of the word, or the graph algorithm sense. \r\n\r\nIn distributed algorithms,
    we looked at two main problems. First, the broadcast problem: given n agents,
    each agent is tasked to forward a (unique) message to every other agent. Agents
    collaborate and can copy and forward all messages they have received up until
    that point. Broadcast is achieved when one agent has successfully broadcast its
    message to everyone else. We studied the case where the communication network
    is controlled by an adversary, under the condition that the graph is rooted in
    every round of communication. We show that the adversary can delay broadcast for
    at most  l\r\n(1 + √\r\n2)n\r\nm\r\n rounds, improving on the $O(n\\log\\log n)$
    previous upper bound~\\cite{fugger2020radius}, and asymptotically matching the
    $\\sim 1.5n$ lower bound~\\cite{schwarz2017linear}.\r\n\r\nWe then looked at the
    stochastic version of the problem: here, the adversary -- parametrized by $k$
    where $k=0$ signifies that the adversary has no control,  and $k=n$ that the adversary
    has full control -- can choose parts of the graph, and the graph is then completed
    stochastically. Here, we are able to look at a stronger version of broadcast:
    instead of having $n$ messages trying to be broadcast in parallel, we can assume
    that only one message needs to be broadcasted. We show the bound $\\Theta(k+\\log
    n)$.\r\n\r\nThen, we looked at undecided states dynamics in population protocols:
    given a population of $n$ agents, where each initially holds an opinion among
    $k$ different ones. In each round, two agents are chosen uniformly at random,
    and can interact. If they have different opinions, they forget their opinions
    and become undecided. If one of them is undecided while the other has an opinion,
    they undecided agent copies they opinion of the decided one. The question is then,
    how many interactions does it take for the whole population to share the same
    opinion? We show a $\\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})$ lower bound
    \ for any $k = o\\left(\\frac {\\sqrt n}{\\log n}\\right)$.\r\nThis is tight for
    any $ k \\le n^{\\frac 1 2 - \\epsilon}$, where $\\epsilon >0$ can be any small
    constant, matching the known $O(kn\\log n)$ upper bound for $k = O\\left(\\frac
    {\\sqrt n} {\\log ^2 n}\\right)$~\\cite{DBLP:conf/podc/AmirABBHKL23}.\r\n\r\nFinally,
    in dynamic algorithms, we study the minimum cut problem: we are given a graph,
    whose vertex set we want to partition into two subsets such that the number of
    edges crossing from one subset to the other is minimized. Then, the graph can
    be updated via edge insertions or deletions, and we must update the solution without
    recomputing everything from scratch. We present an exact fully-dynamic minimum
    cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum
    cut size is at most $2^{\\Theta(\\log^{3/4-c}n)}$ for any $c>0$, improving on
    the previous algorithm~\\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit
    is $(\\log n)^{o(1)}$. Using sparsification and randomization techniques, we are
    able to extend this to all values of the minimum cut in weighted graphs, at the
    cost of a $(1+o(1))$-approximation ratio.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Antoine
      foaf_name: El-Hayek, Antoine
      foaf_surname: El-Hayek
      foaf_workInfoHomepage: http://www.librecat.org/personId=888a098e-fcac-11ee-aff7-d347be57b725
    orcid: 0000-0003-4268-7368
  bibo_doi: 10.15479/AT-ISTA-22281
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/2663-337X
  dct_language: eng
  dct_publisher: Institute of Science and Technology Austria@
  dct_title: 'Handling updates and failures: Dynamic graph algorithms and distributed
    computing on dynamic networks@'
...