Projects per year
Personal profile
Research interests
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.
Further info
I have previously published under the name Sebastian Krinninger.
Further profiles:
- Publications via dblp
- Preprints on arXiv
- Bibliometrics on Google Scholar
- Microblogging on Mastodon
Education/Academic qualification
Computer Science, Dr.techn., Faster Approximation Algorithms for Partially Dynamic Shortest Paths Problems, University of Vienna
1 Oct 2011 → 1 Jun 2015
Award Date: 3 Jun 2015
Computational Intelligence, Dipl.-Ing., Combining Supervaluation and Fuzzy Logic Based Theories of Vagueness, Vienna University of Technology
1 Oct 2008 → 20 Sept 2011
Award Date: 20 Sept 2011
Computer Science, B.Sc., University of Passau
1 Oct 2005 → 23 Sept 2008
Award Date: 23 Sept 2008
External positions
Postdoctoral Researcher, University of Vienna
1 Jan 2017 → 31 Aug 2017
Postdoctoral Researcher, Max-Planck-Institut fur Informatik
1 Jan 2016 → 31 Dec 2016
Postdoctoral Research Fellow, Simons Institute for the Theory of Computing
19 Aug 2015 → 31 Dec 2015
Internship, Microsoft Research Silicon Valley
7 Apr 2014 → 11 Jul 2014
Research Assistant, University of Vienna
1 Sept 2011 → 18 Aug 2015
Keywords
- QA75 Electronic computers. Computer science
- efficient algorithms
- dynamic graph algorithms
- distributed algorithms
- fine-grained complexity
Fields of Science and Technology Classification 2012 (Level 2, 3-digit codes).
- 102 Computer Sciences
-
DynASoAr: Dynamic Algorithms Against Strong Adversaries
Forster, S. (Principal Investigator)
1/09/21 → 31/08/26
Project: Research
-
TRoute: Routing für europäische Bahnverbindungen - Lösungskonzepte
Forster, S. (Principal Investigator)
20/03/23 → 19/11/23
Project: Research
-
TRoute: Routing für europäische Bahnverbindungen - Lösungskonzepte
Loidl, M. (Principal Investigator), Forster, S. (Co-Investigator) & Werner, C. (Co-Investigator)
20/03/23 → 19/11/23
Project: Research
-
DiAloG: Distributed Algorithms for Fundamental Graph Problems
Forster, S. (Principal Investigator)
1/03/20 → 30/09/24
Project: Research
-
Dynamic algorithms for k-center on graphs
Cruciani, E., Forster, S., Goranci, G., Nazari, Y. & Skarlatos, A., 2024, p. 3441-3462. 22 p.Research output: Contribution to conference › Paper › peer-review
-
Fast 2-Approximate All-Pairs Shortest Paths
de Vos, T., Forster, S., Nazari, Y., Dory, M., Kirkpatrick, Y. & Vassilevska Williams, V., 2024, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024.Research output: Chapter in Book/Report/Conference proceeding/Legal commentary › Conference contribution › peer-review
-
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
de Vos, T., Nazari, Y., Forster, S. & Dory, M., 2024, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024.Research output: Chapter in Book/Report/Conference proceeding/Legal commentary › Conference contribution › peer-review
-
Fast Algorithms for Energy Games in Special Cases
Forster, S., Skarlatos, A. & de Vos, T., 30 Sept 2023, Proceedings of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification . Vol. 390. p. 236-252 17 p. (Electronic Proceedings in Theoretical Computer Science, EPTCS).Research output: Chapter in Book/Report/Conference proceeding/Legal commentary › Conference contribution › peer-review
Open Access -
Bootstrapping Dynamic Distance Oracles
Forster, S., Goranci, G., Nazari, Y. & Skarlatos, A., Sept 2023, 31st Annual European Symposium on Algorithms, ESA 2023. Li Gortz, I., Farach-Colton, M., Puglisi, S. J. & Herman, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 50. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 274).Research output: Chapter in Book/Report/Conference proceeding/Legal commentary › Conference contribution › peer-review
Open Access
Activities
-
41st International Symposium on Theoretical Aspects of Computer Science
Forster, S. (Member of programme committee)
23 Sept 2023 → 14 Mar 2024Activity: Participating in or organising an event › Organising an event
-
Dynamic algorithms for k-center on graphs
Forster, S. (Speaker)
19 Sept 2023Activity: Talk or presentation › Oral presentation › science to science / art to art
-
Dynamic Graphs and Algorithm Design
Forster, S. (Organiser)
18 Sept 2023 → 22 Sept 2023Activity: Participating in or organising an event › Organising an event
-
Recent Results on Dynamic Distance Computation
Forster, S. (Speaker)
26 Jun 2023Activity: Talk or presentation › Oral presentation › science to science / art to art
-
Google Switzerland
Forster, S. (Visiting researcher)
5 Jun 2023 → 5 Jul 2023Activity: Research stay › Research Stay › on-site