Sebastian Forster

There is a new website for the research group and myself.

---

News from the Fediverse

---

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.

---

Short 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
  Advisor: Monika Henzinger
  Thesis: Faster Approximation Algorithms for Partially Dynamic Shortest Paths Problems
  Awards: Heinz Zemanek Award (OCG) and Award of Excellence (BMWFW)
• 2008 – 2011 M.Sc. in Computational Intelligence at Vienna University of Technology, Austria
  Thesis: Combining Supervaluation and Fuzzy Logic Based Theories of Vagueness
• 2005 – 2008: B.Sc. in Computer Science at University of Passau, Germany

---

Selected Publications

• Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions (→ arXiv)
  Sebastian Forster and Gramoz Goranci
  51st Annual ACM Symposium on the Theory of Computing (STOC), 2019
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models (→ arXiv)
  Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen
  31st International Symposium on Distributed Computing (DISC), 2017
  SIAM Journal on Computing 50(3), pp. 815–856, 2021
  
• On Fully Dynamic Graph Sparsifiers (→ arXiv)
  Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng
  57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths(→ arXiv)
  Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
  48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2016
  SIAM Journal on Computing 50(3), pp. STOC16-98–STOC16-137, 2021 (STOC 2016 Special Issue)
  
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time (→ arXiv)
  Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
  55th IEEE Symposium on Foundations of Computer Science (FOCS), 2014
  Journal of the ACM 65(6), pp. 36:1–36:40, 2018
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization (→ arXiv)
  Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
  54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013
  SIAM Journal on Computing 45(3), pp. 947–1006, 2016 (FOCS 2013 Special Issue)

For a complete list of publications, please click here or consult DBLP.

---

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

For a more complete list of talks, please click here.

---

Projects

• Dynamic Algorithms Against Strong Adversaries (DynASoAr)
  ERC Starting Grant, 2021 – 2026
• Distributed Algorithms for Fundamental Graph Problems (DiAloG)
  Austrian Science Fund (FWF), 2020 – 2024

---

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

---

Teaching

Courses at University of Salzburg

• Winter 2022/23: VO+PS Advanced Algorithms and Data Structures (with Robert Elsässer)
• Winter 2022/23: UE Problem Solving and Algorithmic Thinking (with Ana Sokolova)
• Summer 2022: VO+PS Algorithmen für verteilte Systeme
• Summer 2022: PS Algorithmen und Datenstrukturen
• Winter 2021/22: VO+PS Formale Sprachen und Komplexitätstheorie
• Winter 2021/22: UE Problem Solving and Algorithmic Thinking (with Ana Sokolova)
• Winter 2021/22: SE Reading Group Algorithms
• Winter 2020/21: VO+PS Advanced Algorithms and Data Structures (with Robert Elsässer)
• Winter 2020/21: UE Problem Solving and Algorithmic Thinking (with Ana Sokolova)
• Summer 2020: VO+PS Algorithmen für verteilte Systeme
• Summer 2020: PS Algorithmen und Datenstrukturen
• Winter 2019/20: UE Problem Solving and Algorithmic Thinking (with Ana Sokolova)
• Winter 2019/20: SE Reading Group Algorithms (with Robert Elsässer)
• Summer 2019: VO+PS Algorithmen für verteilte Systeme
• Summer 2019: PS Algorithmen und Datenstrukturen
• Winter 2018/19: VO+PS Advanced Algorithms and Data Structures (with Robert Elsässer)
• Summer 2018: VO+PS Algorithmen für verteilte Systeme
• Summer 2018: PS Algorithmen und Datenstrukturen
• Winter 2017/18: VO+PS Complexity of Polynomial-Time Problems

Supervision of Theses

Please contact me for a list of available topics for bachelor or master theses. In general, I supervise topics in the following areas: theory, experimental evaluation, and visualization of algorithms.

Completed theses:

• Mara Grilnberger, bachelor thesis: On Thorup-Zwick-based hopsets beyond Huang-Pettie
• Martin Grösbacher, bachelor thesis: A more streamlined exposition to random delay clustering
• Matthias Reichinger, bachelor thesis: Ranking Job Opportunities in a Personalised Career Recommendation System – Learning from Past Staff Movements

Internships

For administrative reasons, I cannot offer paid internships to external students. However, I am happy to host interns that have external funding.

---

I link therefore I am.