Sebastian Forster

---

News via Mastodon

---

Research

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 Sep 2017: Assistant Professor at University of Salzburg (tenure track)
• 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
  Accepted to SIAM Journal on Computing (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

• 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 2019
• A Faster Distributed Single-Source Shortest Paths Algorithm (→ slides)
  59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Paris, France, October 2019
• Towards Optimal Dynamic Graph Compression (→ slides → sources)
  Austrian Computer Science Day, Salzburg, Austria, June 2018
• Brief Announcement: A Note on Hardness of Diameter Approximation (→ slides)
  31st International Symposium on Distributed Computing (DISC), Vienna, Austria, October 2017
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models (→ slides)
  8th Bertinoro Workshop on Algorithms and Data Structures, June 2017

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: 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, SEA
• Journals reviews: SIAM Journal on Computing, Transactions on Algorithms, Algorithmica, Theoretical Computer Science, Theory of Computing Systems, Information Processing Letters, Discussiones Mathematicae Graph Theory
• Reviews for international funding agencies

---

Teaching

Courses at University of Salzburg

• 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

Currently, I do not offer paid internships. However, I am happy to host interns that have their own funding source.

---

I link therefore I am.