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
  • Elisabeth Riedl, administration
  • Emilio Cruciani, postdoc
  • Yasamin Nazari, postdoc
  • Antonis Skarlatos, PhD student
  • Tijn de Vos, PhD student

Former Team Members

  • Judith Warter, administration

Publications

  • Joran van Apeldoorn and Tijn de Vos. “A Framework for Distributed Quantum Queries in the CONGEST Model”. In: Proceedings of the 2022 ACM Symposium on 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: 2022 IEEE 63rd 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: 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: Proceedings of the 2022 ACM Symposium on 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).