Sebastian Forster (né Krinninger)
Affiliation:
University of Salzburg
Department of Computer Sciences
Efficient Algorithms Group
Address:
Room 2.21
Jakob-Haringer-Str. 2
5020 Salzburg, Austria
Email: forster strudel cs.sbg.ac.at
Matrix: @forster:matrix.org
Skype: krinningers
Phone: +43 662 8044-6421
Office hours: by appointment (email)
Pronouns: he, his, him
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
- Winter 2018/19: VO+PS Advanced Algorithms and Data Structures (with Robert Elsässer)
- Winter 202020/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.
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.