Homepage of Sebastian Forster
Contact Information
- Email: forster strudel cs.sbg.ac.at
- Matrix: @forster:matrix.org
- Fediverse:
- Bibliographic Profiles: dblp arXiv Google Scholar Pure
- Phone: +43 662 8044-6421
- Office hours: by appointment (email)
- Pronouns: he, his, him
- Birth name: Sebastian Krinninger
Brief 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, advised by Monika Henzinger
Awards: Heinz Zemanek Award ( OCG) and Award of Excellence ( BMWFW) - 2008 – 2011 M.Sc. in Computational Intelligence at Vienna University of Technology, Austria
- 2005 – 2008: B.Sc. in Computer Science at University of Passau, Germany
Selected Publications
- Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. “Minor Sparsifiers and the Distributed Laplacian Paradigm”. In: Proceedings. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. FOCS 2021 (Denver, CO, USA, Feb. 7–10, 2022). IEEE, 2022, pp. 989–999. doi: 10.1109/FOCS52979.2021.00099. arXiv: 2012.15675.
- Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models”. In: SIAM Journal on Computing 50.3 (2021). Announced at DISC 2017, pp. 815–856. doi: 10.1137/19M1286955. arXiv: 1607.05127.
- Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths”. In: SIAM Journal on Computing 50.3 (2021). Special Section STOC 2016, STOC16-98–STOC16-137. doi: 10.1137/16M1097808. arXiv: 1504.07056.
- Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. “On Fully Dynamic Graph Sparsifiers”. In: Proceedings. 57th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2016 (New Brunswick, NJ, USA, Oct. 9–11, 2016). Ed. by Irit Dinur. IEEE Computer Society, 2016, pp. 335–344. doi: 10.1109/FOCS.2016.44. arXiv: 1604.02094.
- Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the 𝑂(𝑚𝑛) Barrier and Derandomization”. In: SIAM Journal on Computing 45.3 (2016). Special Section FOCS 2013, pp. 947–1006. doi: 10.1137/140957299. arXiv: 1308.0776.
- Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture”. In: Proceedings of the 2015 ACM Symposium on Theory of Computing. STOC 2015 (Portland, OR, USA, June 14–17, 2015). Ed. by Rocco A. Servedio and Ronitt Rubinfeld. ACM, 2015, pp. 21–30. doi: 10.1145/2746539.2746609. arXiv: 1511.06773.
- Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time”. In: Proceedings. 55th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2014 (Philadelphia, PA, USA, Oct. 18–21, 2014). IEEE Computer Society, 2014, pp. 146–155. doi: 10.1109/FOCS.2014.24. arXiv: 1512.08148.
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
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
- Co-organizer of Dagstuhl Seminar Dagstuhl Seminar 22461 “Dynamic Graph Algorithms”
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