Publications

  • Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari, Balasubramanian Sivan, Yifeng Teng, and Creighton Thomas. “Online Allocation and Display Ads Optimization with Surplus Supply”. In: Web and Internet Economics. 18th International Conference. Proceedings. 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.
  • Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. “Computing Smallest Convex Intersecting Polygons”. In: 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: 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.
  • Greg Bodwin, Michael Dinitz, and Yasamin Nazari. “Vertex Fault-Tolerant Emulators”. In: 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: Proceedings. 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, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. “Minor Sparsifiers and the Distributed Laplacian Paradigm”. In: Proceedings. 2021 IEEE 62nd Annual 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: 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: 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.
  • Jakub Lacki and Yasamin Nazari. “Near-Optimal Decremental Hopsets with Applications”. 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, 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: Proceedings 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: Proceedings 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: Proceedings 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: Proceedings of the 51st Annual ACM SIGACT 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: Proceedings. 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.