Homepage of Sebastian Forster

Portrait picture of Sebastian Forster

Contact Information

About Me

I am a professor for computer science at the University of Salzburg, where I teach courses on algorithms. At the department, I serve as the internationalization officer and as the coordinator fo the supplementary study programme “Informatikkompetenz für alle“.

Research Agenda: I perform basic research on the design and analysis of prior-free algorithms with a strong focus on theoretical and mathematical aspects. Motivated by the end of Moore’s Law and the prevalence of “big” and “fast” data, I mainly work an distributed and dynamic algorithms. Most of my algorithms are for the domain of graphs, which are an abstract model for all kinds of networks. Occasionally, I complement my algorithmic work with hardness results in the realm of fine-grained complexity theory. 

Biographical Sketch

  • since Oct 2023: Full Professor at University of Salzburg
  • Jun – Jul 2023: Visiting Faculty Researcher, Google, Zurich, CH
  • Jul 2022 – Sep 2023: 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

  • Dynamic algorithms for k-center on graphs (→  slides →  sources), Workshop on Dynamic Graphs and Algorithm Design, Simons Institute, CA, USA, September 2023
  • Recent Results on Dynamic Distance Computation (→  slides →  sources), ETH Zurich, Switzerland, June 2023
  • Algorithmen sind überall (→  slides →  sources), i-Day, University of Salzburg, Austria, February 2023
  • Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch (→  slides →  sources), Dagstuhl Seminar 22461 “Dynamic Graph Algorithms”, Wadern, Germany, November 2022
  • Distributed Laplacian Solving with Applications (→  slides →  sources), 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022), Paderborn, Germany, June 2022
  • Dynamische Algorithmen: Neue Werkzeuge für Big Data (→  slides →  sources), Roadshow der Jungen Akademie, University of Salzburg, June 2022
  • Fast Dynamic Distance Computation via Dynamic Spanners (→  slides →  sources), Habilitation Colloquium, University of Salzburg, Austria, May 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

Academic Service

  • Program Committee Member: STACS 2024, FOCS 2023, 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, ISAAC, IPEC, ALENEX, APOCS, SEA
  • Journals reviews: Journal of the ACM, 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