Sebastian Forster (né Krinninger)

---

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

---

Teaching

Courses at University of Salzburg

• 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.

Finished:

• 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.

---

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
• A Faster Distributed Single-Source Shortest Paths Algorithm (→ arXiv)
  Sebastian Forster and Danupon Nanongkai
  59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018
• 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: 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

---

I link therefore I am.