Dynamic Algorithms Against Strong Adversaries

This website collects all activity related to the research project “Dynamic Algorithms Against Strong Adversaries (DynASoAr)”. The main objective in this project is to develop faster dynamic graph algorithms that are deterministic or come with worst-case update time guarantees. The project is funded by an ERC Starting Grant.

  • Principal Investigator: Sebastian Forster
  • Host Institution: University of Salzburg
  • Funding Agency: European Research Council (ERC)
  • Project Number: 947702
  • Duration: 09/2021 – 08/2026

Associated Team Members

  • Sebastian Forster, PI
  • Tetiana Mazanko, administration
  • Emilio Cruciani, postdoc
  • Aditi Dudeja, postdoc
  • Antonis Skarlatos, PhD student
  • Tijn de Vos, PhD student

Former Team Members

  • Elisabeth Riedl, administration
  • Judith Warter, administration
  • Yasamin Nazari, postdoc

Publications

  • Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. “On Dynamic Graph Algorithms with Predictions”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 3534–3557. doi:  10.1137/1.9781611977912.126. arXiv:  2307.09961.
  • Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. “Dynamic algorithms for 𝑘-center on graphs”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 3441–3462. doi:  10.1137/1.9781611977912.123. arXiv:  2307.15557.
  • Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, and Tijn de Vos. “Fast 2-Approximate All-Pairs Shortest Paths”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 4728–4757. doi:  10.1137/1.9781611977912.169. arXiv:  2307.09258.
  • Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani, and Francesco Pasquale. “On a Voter Model with Context-Dependent Opinion Adoption”. In: Proc. of the 32nd International Joint Conference on Artificial Intelligence. IJCAI 2023 (Macao, SAR, China, Aug. 19–25, 2023). Announced at AAMAS 2023. ijcai.org, 2023, pp. 38–45. doi:  10.24963/IJCAI.2023/5. arXiv:  2305.07377.
  • Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani, and Francesco Pasquale. “On a Voter Model with Context-Dependent Opinion Adoption”. In: Proc. of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS 2023 (London, United Kingdom, May 29–June 2, 2023). Ed. by Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh. ACM, 2023, pp. 2766–2768. doi:  10.5555/3545946.3599071. arXiv:  2305.07377.
  • Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. “Phase transition of the 𝑘-majority dynamics in biased communication models”. In: Distributed Computing 36.2 (2023). Announced at ICDCN 2021, pp. 107–135. doi:  10.1007/S00446-023-00444-2. arXiv:  2007.15306.
  • Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. “Bootstrapping Dynamic Distance Oracles”. In: Proc. of the 31st Annual European Symposium on Algorithms. ESA 2023 (Amsterdam, The Netherlands, Sept. 4–6, 2023). Ed. by Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman. Vol. 274. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, 50:1–50:16. doi:  10.4230/LIPICS.ESA.2023.50. arXiv:  2303.06102.
  • Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg. “Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch”. In: Proc. of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023 (Orlando, FL, USA, June 20–23, 2023). Ed. by Barna Saha and Rocco A. Servedio. ACM, 2023, pp. 1173–1186. doi:  10.1145/3564246.3585213. arXiv:  2211.04217.
  • Sebastian Forster, Antonis Skarlatos, and Tijn de Vos. “Fast Algorithms for Energy Games in Special Cases”. In: Proc. of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification. GandALF 2023 (Udine, Italy, Sept. 18–20, 2023). Ed. by Antonis Achilleos and Dario Della Monica. Vol. 390. EPTCS. 2023, pp. 236–252. doi:  10.4204/EPTCS.390.15. arXiv:  2307.08442.
  • Sebastian Forster and Tijn de Vos. “Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique”. In: Proc. of the 2023 ACM Symposium on Principles of Distributed Computing. PODC 2023 (Orlando, FL, USA, June 19–23, 2023). Ed. by Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu. ACM, 2023, pp. 75–78. doi:  10.1145/3583668.3594577. arXiv:  2304.02315.
  • Sebastian Forster and Tijn de Vos. “Faster Cut Sparsification of Weighted Graphs”. In: Algorithmica 85.4 (2023). Announced at ICALP 2022, pp. 929–964. doi:  10.1007/S00453-022-01053-4. arXiv:  2112.03120.
  • Tijn de Vos. “Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model”. In: Proc. of the 2023 ACM Symposium on Principles of Distributed Computing. PODC 2023 (Orlando, FL, USA, June 19–23, 2023). Ed. by Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu. ACM, 2023, pp. 71–74. doi:  10.1145/3583668.3594566. arXiv:  2304.01600.
  • Tijn de Vos. “Minimum Cost Flow in the CONGEST Model”. In: Proc. of the 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO 2023 (Alcalá de Henares, Spain, June 6–9, 2023). Ed. by Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti. Vol. 13892. LNCS. Springer, 2023, pp. 406–426. doi:  10.1007/978-3-031-32733-9\_18. arXiv:  2304.01600.
  • Joran van Apeldoorn and Tijn de Vos. “A Framework for Distributed Quantum Queries in the CONGEST Model”. In: Proc. of the 41st ACM Symposium on Principles of Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 109–119. doi:  10.1145/3519270.3538413. arXiv:  2202.10969.
  • Jan van den Brand, Sebastian Forster, and Yasamin Nazari. “Fast Deterministic Fully Dynamic Distance Approximation”. In: Proc. of the 63rd IEEE Annual Symposium on Foundations of Computer Science. FOCS 2022 (Denver, CO, USA, Oct. 31–Nov. 3, 2022). IEEE, 2022, pp. 1011–1022. doi:  10.1109/FOCS54457.2022.00099. arXiv:  2111.03361.
  • Sebastian Forster and Tijn de Vos. “Faster Cut Sparsification of Weighted Graphs”. In: Proc. of the 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (Paris, France, July 4–8, 2022). Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 61:1–61:19. doi:  10.4230/LIPIcs.ICALP.2022.61. arXiv:  2112.03120.
  • Sebastian Forster and Tijn de Vos. “The Laplacian Paradigm in the Broadcast Congested Clique”. In: Proc. of the 41st ACM Symposium on Principles of Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 335–344. doi:  10.1145/3519270.3538436. arXiv:  2205.12059.

Related Activities

  • Co-organization of Dagstuhl Seminar  Dagstuhl Seminar 22461 “Dynamic Graph Algorithms” by Sebastian Forster (Nov 13 – Nov 18, 2022)
  • Rising Stars Talk by Yasamin Nazari at the  Fifth TCS Women Meeting at Theory Fest 2022 (Jun 20, 2022)
  • Organization of science-to-public event  “Roadshow der Jungen Akademie” by Sebastian Forster at University of Salzburg  (Jun 15, 2022)
  • Science-to-public  blog post on algorithms by Sebastian Forster in Junge-Akademie-Blog hosted by derstandard.at (Dec 12, 2021)

Logo of the EU and the ERC

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).