@inproceedings{21916, abstract = {Social network graphs are central to graph learning research, serving as standard benchmarks for algorithm evaluation. However, existing datasets focus mainly on mainstream social media platforms whose structures are shaped notably by algorithmic recommendations. This raises an important question: would alternative, decentralized social networks exhibit different properties? We address this by studying the Fediverse; a collection of decentralized social networks (such as Mastodon and Lemmy). These platforms differ fundamentally from for-profit social media, notably in decentralization and absence of recommendation algorithms, which may yield distinct graph structures. We introduce Fedivertex, a dataset of over 400 graphs from seven decentralized networks, collected weekly over six months. The dataset, released with a companion Python package to facilitate its use, supports research on temporal and structural aspects of decentralized social networks. In particular, we benchmark applications to decentralized machine learning and community detection.}, author = {Damie, Marc and Cyffers, Edwige Audrey Lucienne}, booktitle = {2026 Proceedings of the ACM Web Conference}, isbn = {9798400723070}, location = {Dubai}, pages = {8393--8396}, publisher = {ACM}, title = {{Fedivertex: A graph dataset based on decentralized Social Media}}, doi = {10.1145/3774904.3792868}, year = {2026}, } @inproceedings{22327, abstract = {Population protocols are a model of distributed computing where 𝑛 agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) interaction scheduler. This model was intensively studied in recent years; in particular, the problem of relative majority received much attention: Each agent starts with an input opinion (or color) out of 𝑘 possibilities, and the goal is for each agent to eventually output the color with the largest support in the population. Before our work, the state complexity (the minimum number of states required per agent) was only known to be between Ω(𝑘 2 ) and𝑂(𝑘 7 ). Our main contribution is a population protocol that solves the relative majority problem with 𝑘 3 states. We achieve this result with a new protocol called Circles. While prior approaches in the literature relied on duels of agents to find the majority color — an approach that proved effective for the case with two colors — Circles partitions the agents into circular linked lists of decreasing sizes, with the property that no two agents with the same initial color lie in the same circle. We show that Circles always correctly computes the desired structure against the most adversarial of schedulers (weakly fair). We then show that a trivial extension of Circles solves the relative majority problem. We extend our protocol to handle various tie-breaking mechanisms or to support the case where the agents do not share a prior ordering of the colors. Finally, we show that a modification of Circles solves the ranking problem with 2 · 𝑘^4 states, where each agent must output the rank of its initial color in the population.}, author = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, isbn = {9798400725128}, location = {Egham, United Kingdom}, pages = {414 -- 424}, publisher = {Association for Computing Machinery}, title = {{Ranking opinions with few states in population protocols}}, doi = {10.1145/3796701.3815913}, year = {2026}, } @article{14703, abstract = {We present a discretization of the dynamic optimal transport problem for which we can obtain the convergence rate for the value of the transport cost to its continuous value when the temporal and spatial stepsize vanish. This convergence result does not require any regularity assumption on the measures, though experiments suggest that the rate is not sharp. Via an analysis of the duality gap we also obtain the convergence rates for the gradient of the optimal potentials and the velocity field under mild regularity assumptions. To obtain such rates we discretize the dual formulation of the dynamic optimal transport problem and use the mature literature related to the error due to discretizing the Hamilton-Jacobi equation.}, author = {Ishida, Sadashige and Lavenant, Hugo}, issn = {1615-3383}, journal = {Foundations of Computational Mathematics}, keywords = {Optimal transport, Hamilton-Jacobi equation, convex optimization}, pages = {349--384}, publisher = {Springer Nature}, title = {{Quantitative convergence of a discretization of dynamic optimal transport using the dual formulation}}, doi = {10.1007/s10208-024-09686-3}, volume = {26}, year = {2026}, } @article{20851, abstract = {High-voltage disordered spinel LiNi0.5Mn1.5O4 is a promising cathode material for high power density in lithium-ion batteries. However, it suffers from poor cycle life associated with the rock-salt phase transformation. This study presents a straightforward synthesis approach to enhance the electrochemical performance of LiNi0.5Mn1.5O4 through a synergistic solid-state modification with LiF and AlF3. This dual modification promotes rapid Liâș diffusion, enables near-complete delithiation/lithiation, approaching the theoretical capacity of disordered LiNi0.5Mn1.5O4, and, more importantly, effectively mitigates the formation of the rock-salt phase, thereby enhancing structural stability, as confirmed by operando X-ray absorption spectroscopy (XAS) and synchrotron X-ray diffraction (SXRD). As a result, the optimized LiNi0.5Mn1.5O4 (10 mg AlF3 + 30 mg LiF) delivers high reversible capacities of 142.1, 139.1, 129.2, 121.6, 110.3, 93.5, and 76.1 mAh∙g−1 at 0.2C, 0.5C, 1.0C, 2.0C, 3.0C, 4.0C, and 5.0C, respectively. Full cells using graphite as the anode and a high-loading cathode exhibit excellent cycling performance. They retain 80% of their capacity after 200 cycles at 0.5C within a voltage window of 3.5–4.9 V with cathode loading of 11 mg∙cm−2. The findings of this study will significantly advance high-power LiNi0.5Mn1.5O4 materials, offering improved battery life and thereby enhancing their potential for practical applications.}, author = {Chang, Xingqi and Escudero, Carlos and Black, Ashley P. and Horta, Sharona and MartĂ­nez, ElĂ­as and Lu, Xuan and Llorca, Jordi and Ibåñez, Maria and Biendicho, Jordi Jacas and Cabot, Andreu}, issn = {2198-3844}, journal = {Advanced Science}, keywords = {disordered spinel LiNi0.5Mn1.5O4 (LNMO), generation 3b batteries, operando SXRD, operando XAS, rock-salt, solid-state synthesis}, number = {11}, publisher = {Wiley}, title = {{Mitigating the rock-salt phase transformation in disordered LNMO through synergetic solid-state AlF3/LiF modifications}}, doi = {10.1002/advs.202515962}, volume = {13}, year = {2026}, } @article{20859, abstract = {Effective immune responses rely on the efficient migration of leukocytes. Yet, how temperature regulates migration dynamics at the single-cell level has remained poorly understood. Using zebrafish embryos and mouse tissue explants, we found that temperature positively regulates leukocyte migration speed, exploration, and arrival frequencies to wounds and lymph vessels. Complementary 2D and 3D cultures revealed that this thermokinetic control of cell migration is conserved across immune cell types, independently of the 3D tissue environment. By applying precise (sub-)cellular temperature modulation, we identified a rapid and reversible thermo-response that depends on myosin II activity. Small physiological increases in temperature (1°C –2°C), as present during fever-like conditions, profoundly increased immune responses by accelerating arrival times at lymphatic vessels and tissue wounds. These findings identify myosin-II-dependent actomyosin contractility as a critical mechanical structure regulating single-cell thermo-adaptability, with physiological implications for tuning the speed of immune responses in vivo.}, author = {Company-Garrido, IvĂĄn and Zurita Carpio, Alberto and Colomer-Rosell, Mariona and Ciraulo, Bernard and Molkenbur, Ronja and Lanzerstorfer, Peter and Pezzano, Fabio and Agazzi, Costanza and Hauschild, Robert and Jain, Saumey and Jacques, Jeroen M. and Venturini, Valeria and Knapp, Christian and Xie, Yufei and Merrin, Jack and Weghuber, Julian and Schaaf, Marcel and Quidant, Romain and Kiermaier, Eva and Ortega Arroyo, Jaime and Ruprecht, Verena and Wieser, Stefan}, issn = {1878-1551}, journal = {Developmental Cell}, keywords = {thermobiology, cell migration, thermo-adaptability of immune cells}, number = {2}, pages = {356--371.e12}, publisher = {Elsevier}, title = {{Myosin II regulates cellular thermo-adaptability and the efficiency of immune responses}}, doi = {10.1016/j.devcel.2025.10.006}, volume = {61}, year = {2026}, } @article{20933, abstract = {Photo-responsive systems based on azobenzenes usually require UV light for E→Z isomerization, limiting their applicability, especially in biomedical contexts. Disequilibration by sensitization of azobenzene under confinement (DESC) has recently emerged as a supramolecular strategy to bypass this limitation without the need to derivatize the azobenzene scaffold. Here, we expand DESC to water-soluble azopolymers obtained by RAFT polymerization and systematically investigate the interplay between the polymer structure and DESC efficiency. Using this approach, we achieved as much as 85% of the direct photoexcitation (UV) switching efficiency, while utilizing low-energy (yellow) light. These results establish general design principles for combining DESC with polymeric systems, opening new opportunities for the development of functional materials driven with low-energy light.}, author = {Meteling, Henning Jörn and Gemen, Julius and HĂ€kkinen, Satu and Klajn, Rafal and Priimagi, Arri}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {7}, publisher = {Wiley}, title = {{Sensitized disequilibration of water-soluble azopolymers}}, doi = {10.1002/anie.202523447}, volume = {65}, year = {2026}, } @article{20925, abstract = {We prove normal typicality and dynamical typicality for a (centered) random block-band matrix model with block-dependent variances. A key feature of our model is that we achieve intermediate equilibration times, an aspect that has not been proven rigorously in any model before. Our proof builds on recently established concentration estimates for products of resolvents of Wigner type random matrices (ErdƑs and Riabov in Commun Math Phys 405(12): 282, 2024) and an intricate analysis of the deterministic approximation.}, author = {Erdös, LĂĄszlĂł and Henheik, Sven Joscha and Vogel, Cornelia}, issn = {1573-0530}, journal = {Letters in Mathematical Physics}, publisher = {Springer Nature}, title = {{Normal typicality and dynamical typicality for a random block-band matrix model}}, doi = {10.1007/s11005-025-02037-5}, volume = {116}, year = {2026}, } @article{20924, abstract = {Pioneer transcription factors (TFs) possess the ability to read out DNA motifs embedded within nucleosomes, driving changes in gene expression during cellular differentiation and reprogramming. Here, we present selected engagement on nucleosome sequencing (SeEN-seq), a protocol designed to systematically identify potential TF-binding sites on the nucleosome. We describe steps for nucleosome library assembly, SeEN-seq assay, and cryoelectron microscopy (cryo-EM) sample preparation. This protocol facilitates the preparation of homogeneous pioneer TF-nucleosome complexes for cryo-EM structure determination using single-particle analysis. For complete details on the use and execution of this protocol, please refer to Michael et al.1}, author = {Kobayashi, Wataru and Michael, Alicia and Ruangroengkulrith, Siwat and KĂŒmmecke, Maximilian and Tachibana, KikuĂ«}, issn = {2666-1667}, journal = {STAR Protocols}, number = {1}, publisher = {Elsevier}, title = {{Protocol for integrative analysis of transcription factor-nucleosome interactions using SeEN-seq and cryo-EM structure determination}}, doi = {10.1016/j.xpro.2025.104295}, volume = {7}, year = {2026}, } @article{17437, abstract = {We prove that the zero-fiber of the moment map of a totally negative quiver has rational singularities. Our proof consists in generalizing dimension bounds on jet spaces of this fiber, which were introduced by Budur. We also transfer the rational singularities property to other moduli spaces of objects in 2-Calabi-Yau categories, based on recent work of Davison. This has interesting arithmetic applications on quiver moment maps and moduli spaces of objects in 2-Calabi-Yau categories. First, we generalize results of Wyss on the asymptotic behaviour of counts of jets of quiver moment maps over finite fields. Moreover, we interpret the limit of counts of jets on a given moduli space as its p-adic volume under a canonical measure analogous to the measure built by Carocci, Orecchia and Wyss on certain moduli spaces of coherent sheaves.}, author = {Vernet, Tanguy}, issn = {1531-586X}, journal = {Transformation Groups}, pages = {1047--1083}, publisher = {Springer Nature}, title = {{Rational singularities for moment maps of totally negative quivers}}, doi = {10.1007/s00031-024-09873-0}, volume = {31}, year = {2026}, } @article{20973, abstract = {CuAgSe-based materials are attractive for low-temperature thermoelectric (TE) applications but are limited by bipolar conduction and relatively high thermal conductivity. Herein, we report a ligand-free aqueous synthesis of Te-doped CuAgSe (CuAgSe1-xTex), where structural and electronic modulation improve carrier transport and suppress phonon propagation. Ex-situ time-resolved X-ray diffraction reveals a spontaneous growth mechanism, while density functional theory calculations show that Te-5s and 5p orbitals hybridization generates localized states and an asymmetric density of states, thereby enhancing the Seebeck coefficient. Electron microscopy and strain analyses confirm that Te-doping introduces a high density of lattice dislocations and grain boundaries, leading to a reduced lattice thermal conductivity of 0.11 W m−1K−1 at 443 K. These synergistic effects translate into device-level performance—the first integrated CuAgSe thermoelectric modules, exhibit a maximum cooling temperature difference of 27.3 K, and power density of 0.34 W cm−2 with a conversion efficiency of 3.6% at a modest temperature gradient of 136 K. These results demonstrate that CuAgSe1-xTex enables efficient energy harvesting and localized cooling under small temperature gradient, underscoring the importance of structural and electronic design beyond conventional zT benchmarks.}, author = {Meng, Weite and Li, Mingquan and Wang, Qingyue and Song, Pingan and Yang, Xuan and Wang, Wen Jun and Hong, Min and Ibåñez, Maria and Cabot, Andreu and Zhang, Yu and Liu, Yu and Lim, Khak Ho}, issn = {1613-6829}, journal = {Small}, number = {25}, publisher = {Wiley}, title = {{Efficient near room temperature thermoelectric cooling and power generation with CuAgSe}}, doi = {10.1002/smll.202513035}, volume = {22}, year = {2026}, } @article{21017, abstract = {With the growing interest in blockchains, permissioned approaches to consensus have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. In fact, many state-of-the-art BFT consensus algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which limits the throughput for deeper trees. In this paper we propose Kauri, a BFT communication abstraction that sustains high throughput as the system size grows by leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Furthermore, when the number of faults is moderate (arguably the most common case in practice), our construction is able to recover from faults in an optimal number of reconfiguration steps. We implemented and experimentally evaluated Kauri with up to 800 processes. Our results show that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, by up to 58x without compromising latency. Interestingly, in some cases, the parallelization provided by Kauri can also decrease the latency.}, author = {Neiheiser, Ray and Matos, Miguel and Rodrigues, Luis}, issn = {1557-7333}, journal = {ACM Transactions on Computer Systems}, keywords = {Distributed systems, byzantine fault tolerance, blockchain, vote aggregation, pipelining}, number = {2}, publisher = {Association for Computing Machinery}, title = {{Kauri: BFT consensus with pipelined tree-based dissemination and aggregation}}, doi = {10.1145/3769423}, volume = {44}, year = {2026}, } @article{14278, abstract = {The Birkhoff conjecture says that the boundary of a strictly convex integrable billiard table is necessarily an ellipse. In this article, we consider a stronger notion of integrability, namely, integrability close to the boundary, and prove a local version of this conjecture: a small perturbation of almost every ellipse that preserves integrability near the boundary, is itself an ellipse. We apply this result to study local spectral uniqueness of ellipses using the connection between the wave trace of the Laplacian and the dynamics near the boundary and establish local uniqueness for almost all of them.}, author = {Koval, Illya}, issn = {1432-1297}, journal = {Inventiones Mathematicae}, pages = {221--298}, publisher = {Springer Nature}, title = {{Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse}}, doi = {10.1007/s00222-025-01397-y}, volume = {244}, year = {2026}, } @article{21264, abstract = {Rodents' ability to encode the whisking phase has been extensively documented through neuronal recordings from ascending sensory pathways. Yet, while indicating that reafference originates from the mechanoreceptors, the mechanistic underpinnings of the whisking phase encoding within the follicle remain unclear. Here we present anatomical, histological, and biomechanical evidence for the presence of a distinctive elastic segment (ES) within the basal part of the whisker shaft inside the follicle. This ES, composed of immature keratin, is capable of both bending and twisting. Forces generated by whisker movement deform this segment, causing whisker shaft deflections that can stimulate specific mechanoreceptor subsets within the follicle at different phases of the whisking cycle. This mechanism appears to operate during both free‐air whisking and object contact. We propose that the ES enables torsion‐based mechanoreceptor activation, allowing encoding of the whisking phase.}, author = {Haidarliu, Sebastian and Nelinger, Guy and Gantar, Luka and Ahissar, Ehud and Saraf‐Sinik, Inbar}, issn = {1932-8494}, journal = {The Anatomical Record}, number = {7}, pages = {1910--1924}, publisher = {Wiley}, title = {{An elastic segment of the whisker shaft enables coding of the whisking phase via whisker torsion in rats and mice}}, doi = {10.1002/ar.70051}, volume = {309}, year = {2026}, } @article{20078, abstract = {Let A be an abelian variety defined over a number field K, E/K be an elliptic curve, and ϕ : A → Em be an isogeny defined over K. Let P ∈ A(K) be such that ϕ(P)=(Q1,..., Qm) with RankZ(⟹Q1,...,Qm⟩)=1. We will study a divisibility sequence related to the point P and show its relation with elliptic divisibility sequences.}, author = {BaraƄczuk, Stefan and Naskręcki, Bartosz and Verzobio, Matteo}, issn = {0022-314X}, journal = {Journal of Number Theory}, keywords = {Divisibility sequences, Abelian varieties, Elliptic divisibility sequences, Isogenies, Primitive divisors}, pages = {170--183}, publisher = {Elsevier}, title = {{Divisibility sequences related to abelian varieties isogenous to a power of an elliptic curve}}, doi = {10.1016/j.jnt.2025.06.001}, volume = {279}, year = {2026}, } @article{20191, abstract = {High-entropy alloys (HEAs) show great potential for catalyzing complex multi-step reactions, but optimizing their parameters, i.e., composition, but also their crystallinity and morphology, remains a significant challenge. In this study, FeCoNiMoW HEAs are synthesized into either amorphous nanosheets (HEANS) or crystalline nanoparticles (HEANP), which are then used to catalyze the lithium–sulfur (Li–S) reaction of Li–S batteries (LSBs). Evaluations in symmetric cells, coin cells, and pouch cells reveal that HEANS significantly enhance LSB performance, achieving initial discharge capacities up to 1632 mAh g−1. The batteries also exhibit excellent cycling stability over 1000 cycles at 3Cand maintain high-rate performance up to 10C with a capacity of 614 mAh g−1. Comprehensive in situ analyses and density functional theory calculations demonstrate that amorphous HEANS provide more active sites, better ionic conductivity and stronger chemical interactions with lithium polysulfides (LiPS). These properties effectively suppress the shuttle effect, promote the complete S8 → Li2S conversion by reducing the impedance of the solid-electrolyte interphase, and accelerate the Li2S4 → Li2S2 step by lowering the nucleation energy barrier. Overall, this study highlights the superior catalytic properties of amorphous 2D HEAs in LSBs and offers new insights into the mechanisms of LiPS conversion.}, author = {He, Ren and Lee, Seungho and Ding, Yang and Huang, Chen and Lu, Xuan and Zheng, Lirong and Yu, Ao and Zhang, Chaoyue and Li, Canhuang and Bi, Xiaoyu and Li, Yaqiang and Liao, Yaqi and Li, Junshan and Ostovari Moghaddam, Ahmad and Yernar, Salimov and Xu, Ying and Ibåñez, Maria and Zhang, Chaoqi and Yang, Linlin and Zhou, Yingtang and Cabot, Andreu}, issn = {1616-3028}, journal = {Advanced Functional Materials}, keywords = {amorphous, high entropy alloy, in situ electrochemical impedance spec-troscopy, in situ Raman, Li–S batteries}, number = {5}, publisher = {Wiley}, title = {{Amorphous high entropy alloy nanosheets enabling robust Li–S batteries}}, doi = {10.1002/adfm.202513859}, volume = {36}, year = {2026}, } @article{20590, abstract = {Moist convection is a fundamental process occurring in the Earth's atmosphere. It plays a central role in the weather and climate of the Tropics, where, to first order, the heating of the atmosphere by convection is in balance with the cooling of the atmosphere by the emission of radiation to outer space. In this study, we use a cloud-resolving model in radiative–convective equilibrium with an imposed constant rate of radiative cooling and study the response of moist convection to varying this rate of radiative cooling. In particular, we study two types of simulation: varying air temperature (VAT) simulations, where the air temperature is allowed to adjust to the imposed radiative cooling, and constant air temperature (CAT) simulations, where the surface temperature is tuned to ensure that the atmospheric temperature profile in the domain is constant. We recover the previously known result that, in response to increasing radiative cooling, the area of convection expands rapidly, while the intensity of convection does not change. We find that this response is explained by the increased boundary-layer variability in simulations with greater radiative cooling, which compensates for the decreasing temperature by adding a larger initial velocity close to the cloud base. We also propose a fundamental scaling of the non-dimensional cumulus mass flux in moist convection, which is robust across models of different complexity. We aim to bridge the gap between highly idealised prototypes of moist convection, such as the “Rainy–BĂ©nard convection” introduced by Vallis et al., and comprehensive cloud-resolving models.}, author = {Agasthya, Lokahith N and Muller, Caroline J}, issn = {1477-870X}, journal = {Quarterly Journal of the Royal Meteorological Society}, number = {775}, publisher = {Wiley}, title = {{Moist convection and radiative cooling: Dynamical response and scaling}}, doi = {10.1002/qj.70044}, volume = {152}, year = {2026}, } @article{20585, abstract = {Motivated by applications in medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, kernels and cokernels, we design provably stable homological quantifiers that describe the geometric micro- and macro-structure of how the color classes mingle. These can be efficiently computed using chromatic variants of Delaunay and alpha complexes, and code that does these computations is provided.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {2639-8001}, journal = {Foundations of Data Science}, keywords = {Topological data analysis, Delaunay mosaic, alpha complex, chromatic sets, persistent homology, kernel/image/cokernel persistent homology, radius function, discrete Morse theory, exact sequences}, pages = {30--62}, publisher = {American Institute of Mathematical Sciences}, title = {{Chromatic alpha complexes}}, doi = {10.3934/fods.2025003}, volume = {8}, year = {2026}, } @article{20490, abstract = {We study flips in hypertriangulations of planar points sets. Here a level-k hypertriangulation of n points in the plane is a subdivision induced by the projection of a k-hypersimplex, which is the convex hull of the barycenters of the (k-1)-dimensional faces of the standard (n-1)-simplex. In particular, we introduce four types of flips and prove that the level-2 hypertriangulations are connected by these flips. }, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafari, Mohadese and Heiss, Teresa and Saghafian, Morteza}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Flips in two-dimensional hypertriangulations}}, doi = {10.1016/j.ejc.2025.104248}, volume = {132}, year = {2026}, } @article{20081, abstract = {Information measures can be constructed from RĂ©nyi divergences much like mutual information from Kullback-Leibler divergence. One such information measure is known as Sibson α-mutual information and has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this paper, we survey and extend the state of the art. In particular, we introduce variational representations for Sibson α-mutual information and employ them in each described context to derive novel results. Namely, we produce generalized Transportation-Cost inequalities and Fano-type inequalities. We also present an overview of known applications, spanning from learning theory and Bayesian risk to universal prediction.}, author = {Esposito, Amedeo Roberto and Gastpar, Michael and Issa, Ibrahim}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {7}, pages = {4434--4467}, publisher = {IEEE}, title = {{Sibson α-mutual information and its variational representations}}, doi = {10.1109/TIT.2025.3587340}, volume = {72}, year = {2026}, } @phdthesis{22281, 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. In 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 (1 + √ 2)n m 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}. We 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)$. Then, 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)$. This 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}. Finally, 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.}, author = {El-Hayek, Antoine}, issn = {2663-337X}, pages = {244}, publisher = {Institute of Science and Technology Austria}, title = {{Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks}}, doi = {10.15479/AT-ISTA-22281}, year = {2026}, }