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.
Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari, Balasubramanian Sivan, Yifeng Teng, and Creighton Thomas. “Online Allocation and Display Ads Optimization with Surplus Supply”. In: Proc. of the 18th Conference on Web and Internet Economics. WINE 2022 (Troy, NY, USA, Dec. 12–15, 2022). Ed. by Kristoffer Arnsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian. Vol. 13778. LNCS. Springer, 2022, pp. 41–59. doi: 10.1007/978-3-031-22832-2\_3. arXiv: 2107.06980.
Aris Anagnostopoulos, Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. “Biased opinion dynamics: when the devil is in the details”. In: Information Sciences 593 (2022), pp. 49–63. doi: 10.1016/J.INS.2022.01.072. arXiv: 2008.13589.
Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. “Computing Smallest Convex Intersecting Polygons”. In: Proc. of the 30th Annual European Symposium on Algorithms. ESA 2022 (Berlin/Potsdam, Germany, Sept. 5–9, 2022). Ed. by Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman. Vol. 244. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 9:1–9:13. doi: 10.4230/LIPIcs.ESA.2022.9. arXiv: 2208.07567.
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.
Greg Bodwin, Michael Dinitz, and Yasamin Nazari. “Vertex Fault-Tolerant Emulators”. In: Proc. of the 13th Innovations in Theoretical Computer Science Conference. ITCS 2022 (Berkeley, CA, USA, Jan. 31–Feb. 3, 2022). Ed. by Mark Braverman. Vol. 215. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 25:1–25:22. doi: 10.4230/LIPIcs.ITCS.2022.25. arXiv: 2109.08042.
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, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. “Minor Sparsifiers and the Distributed Laplacian Paradigm”. In: Proc. of the 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS 2021 (Denver, CO, USA, Feb. 7–10, 2022). IEEE, 2022, pp. 989–999. doi: 10.1109/FOCS52979.2021.00099. arXiv: 2012.15675.
Sebastian Forster, Martin Grösbacher, and Tijn de Vos. “An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions”. In: Proc. of the 25th International Conference on Principles of Distributed Systems. OPODIS 2021 (Strasbourg, France, Dec. 13–15, 2021). Ed. by Quentin Bramas, Vincent Gramoli, and Alessia Milani. Vol. 217. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 16:1–16:17. doi: 10.4230/LIPIcs.OPODIS.2021.16. arXiv: 2111.08975.
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.
Jakub Lacki and Yasamin Nazari. “Near-Optimal Decremental Hopsets with Applications”. 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, 86:1–86:20. doi: 10.4230/LIPIcs.ICALP.2022.86. arXiv: 2009.08416.
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models”. In: SIAM Journal on Computing 50.3 (2021). Announced at DISC 2017, pp. 815–856. doi: 10.1137/19M1286955. arXiv: 1607.05127.
Aaron Bernstein, Sebastian Forster, and Monika Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching”. In: ACM Transactions on Algorithms 17.4 (2021). Announced at SODA 2019, 29:1–29:51. doi: 10.1145/3469833. arXiv: 1810.10932.
Sebastian Forster, Gramoz Goranci, and Monika Henzinger. “Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications”. In: Proc. of the 2021 ACM-SIAM Symposium on Discrete Algorithms. SODA 2021 (Virtual Conference, Jan. 10–13, 2021). Ed. by Dániel Marx. SIAM, 2021, pp. 1226–1245. doi: 10.1137/1.9781611976465.75. arXiv: 2004.10319.
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths”. In: SIAM Journal on Computing 50.3 (2021). Special Section STOC 2016, STOC16-98–STOC16-137. doi: 10.1137/16M1097808. arXiv: 1504.07056.
Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. “Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms”. In: Proc. of the 2020 ACM-SIAM Symposium on Discrete Algorithms. SODA 2020 (Salt Lake City, UT, USA, Jan. 5–8, 2020). Ed. by Shuchi Chawla. SIAM, 2020, pp. 2046–2065. doi: 10.1137/1.9781611975994.126. arXiv: 1910.14344.
Aaron Bernstein, Sebastian Forster, and Monika Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching”. In: Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2019 (San Diego, California, Jan. 6–9, 2019). Ed. by Timothy M. Chan. SIAM, 2019, pp. 1899–1918. doi: 10.1137/1.9781611975482.115. arXiv: 1810.10932.
Sebastian Forster and Gramoz Goranci. “Dynamic low-stretch trees via dynamic low-diameter decompositions”. In: Proc. of the 51st Annual ACM Symposium on Theory of Computing. STOC 2019 (Phoenix, AZ, USA, June 23–26, 2019). Ed. by Moses Charikar and Edith Cohen. ACM, 2019, pp. 377–388. doi: 10.1145/3313276.3316381. arXiv: 1804.04928.
Karl Bringmann and Sebastian Krinninger. “A note on hardness of diameter approximation”. In: Information Processing Letters 133 (2018), pp. 10–15. doi: 10.1016/j.ipl.2017.12.010. arXiv: 1705.02127.
Sebastian Forster and Danupon Nanongkai. “A Faster Distributed Single-Source Shortest Paths Algorithm”. In: Proc. of the 59th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2018 (Paris, France, Oct. 7–9, 2018). Ed. by Mikkel Thorup. IEEE Computer Society, 2018, pp. 686–697. doi: 10.1109/FOCS.2018.00071. arXiv: 1711.01364.
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time”. In: Journal of the ACM 65.6 (2018). Announced at FOCS 2014, 36:1–36:40. doi: 10.1145/3218657. arXiv: 1512.08148.