Homepage of Sebastian Forster

Portrait picture of Sebastian Forster

Contact Information

Brief Biography

  • since Jul 2022: Associate Professor at University of Salzburg
  • Sep 2017 – Jan 2022: Assistant Professor at University of Salzburg
  • Jan 2016 – Aug 2017:  PostDoc, first at Max Planck Institute for Informatics, then at University of Vienna
  • Aug – Dec 2015: Research Fellow at the Simons Institute for the Theory of Computing, Berkeley, USA
  • Apr – Jul 2014: Internship at Microsoft Research, Silicon Valley Lab, Mountain View, USA
  • 2011 – 2015: Ph.D. in Computer Science at University of Vienna, Austria, advised by  Monika Henzinger
    Awards: Heinz Zemanek Award ( OCG) and Award of Excellence ( BMWFW)
  • 2008 – 2011 M.Sc. in Computational Intelligence at Vienna University of Technology, Austria
  • 2005 – 2008: B.Sc. in Computer Science at University of Passau, Germany

Selected Publications

  • 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.
  • 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.
  • 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.
  • Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. “On Fully Dynamic Graph Sparsifiers”. In: Proceedings. 57th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2016 (New Brunswick, NJ, USA, Oct. 9–11, 2016). Ed. by Irit Dinur. IEEE Computer Society, 2016, pp. 335–344. doi:  10.1109/FOCS.2016.44. arXiv:  1604.02094.
  • Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the 𝑂(𝑚𝑛) Barrier and Derandomization”. In: SIAM Journal on Computing 45.3 (2016). Special Section FOCS 2013, pp. 947–1006. doi:  10.1137/140957299. arXiv:  1308.0776.
  • Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture”. In: Proceedings of the 2015 ACM Symposium on Theory of Computing. STOC 2015 (Portland, OR, USA, June 14–17, 2015). Ed. by Rocco A. Servedio and Ronitt Rubinfeld. ACM, 2015, pp. 21–30. doi:  10.1145/2746539.2746609. arXiv:  1511.06773.
  • Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time”. In: Proceedings. 55th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2014 (Philadelphia, PA, USA, Oct. 18–21, 2014). IEEE Computer Society, 2014, pp. 146–155. doi:  10.1109/FOCS.2014.24. arXiv:  1512.08148.

Recent Talks

  • Distributed Laplacian Solving with Applications (→  slides →  sources) 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022), Paderborn, Germany, June 2022
  • Fast Deterministic Fully Dynamic Distance Approximation (→  slides →  sources) 3rd European Meeting on Algorithmic Challenges of Big Data (ACBD 2022), IDEAS NCBR, Warsaw, Poland, May 2022
  • Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms (→  slides →  sources) Workshop on Recent Trends in Theoretical Computer Science, TTIC, Chicago, IL, USA, January 2020
  • Single-Source Shortest Paths: Towards Optimality (→  slides) Workshop on Advances in Distributed Graph Algorithms (ADGA), New Orleans, LA, USA, October 2018
  • A Faster Distributed Single-Source Shortest Paths Algorithm (→  slides) 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Paris, France, October 2018
  • Towards Optimal Dynamic Graph Compression (→  slides →  sources) Austrian Computer Science Day, Salzburg, Austria, June 2018

Academic Service

  • Program Committee Member: ICALP 2023, SWAT 2022, SIROCCO 2022, SOSA 2022, DISC 2020, STOC 2020, ESA 2018
  • Conferences: External reviews for all major algorithms conferences: STOC, FOCS, SODA, ICALP, ESA, ITCS, SPAA, PODC, DISC, SoCG, STACS, IPEC, ALENEX, APOCS, SEA
  • Journals reviews: SIAM Journal on Computing, Transactions on Algorithms, Algorithmica, Theoretical Computer Science, Journal of Computer and System Sciences, Theory of Computing Systems, Information Processing Letters, Discussiones Mathematicae Graph Theory
  • Reviews for international funding agencies: BSF, ISF, NCN
  • Co-organizer of Dagstuhl Seminar   Dagstuhl Seminar 22461 “Dynamic Graph Algorithms”

Courses at University of Salzburg