Sebastian Forster

Ass.-Prof. Dipl.-Ing. Dr., BSc.

  • Jakob-Haringer-Str. 2

    5020 Salzburg

    Austria

20092020

Research output per year

If you made any changes in Pure these will be visible here soon.

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:

Education/Academic qualification

Computer Science, Dr.techn., University of Vienna

1 Oct 20111 Jun 2015

Award Date: 3 Jun 2015

Computational Intelligence, Dipl.-Ing., Vienna University of Technology

1 Oct 200820 Sep 2011

Award Date: 20 Sep 2011

Computer Science, B.Sc., University of Passau

1 Oct 200523 Sep 2008

Award Date: 23 Sep 2008

External positions

Postdoctoral Researcher, University of Vienna

1 Jan 201731 Aug 2017

Postdoctoral Researcher, Max-Planck-Institut fur Informatik

1 Jan 201631 Dec 2016

Postdoctoral Research Fellow, Simons Institute for the Theory of Computing

19 Aug 201531 Dec 2015

Internship, Microsoft Research Silicon Valley

7 Apr 201411 Jul 2014

Research Assistant, University of Vienna

1 Sep 201118 Aug 2015

Fields of Science and Technology Classification 2012 (Level 2, 3-digit codes).

  • 102 Computer Sciences

Keywords

  • QA75 Electronic computers. Computer science
  • efficient algorithms
  • dynamic graph algorithms
  • distributed algorithms
  • fine-grained complexity

Projects

Research Output

  • 22 Conference contribution
  • 8 Article

A deamortization approach for dynamic spanner and dynamic maximal matching

Bernstein, A., Forster, S. & Henzinger, M., 1 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Chan, T. (ed.). SIAM, p. 1899-1918 20 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Dynamic low-stretch trees via dynamic low-diameter decompositions

Forster, S. & Goranci, G., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 377-388 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

A faster distributed single-source shortest paths algorithm

Forster, S. & Nanongkai, D., 30 Nov 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 686-697 12 p. 8555149. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

A note on hardness of diameter approximation

Bringmann, K. & Krinninger, S., 2018, In : Information Processing Letters. 133, p. 10-15 6 p.

Research output: Contribution to journalArticle

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

Henzinger, M., Krinninger, S. & Nanongkai, D., 1 Nov 2018, In : Journal of the ACM. 65, 6, p. 36:1-36:40 36.

Research output: Contribution to journalArticle

Open Access

Activities

  • 5 Oral presentation
  • 2 Membership of committee

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

Sebastian Forster (Speaker)

31 Jan 2020

Activity: Talk or presentationOral presentationscience to science / art to art

Annual ACM Symposium on Theory of Computing (Event)

Sebastian Forster (Member)

6 Aug 201926 Jun 2020

Activity: MembershipMembership of committee

A Faster Distributed Single-Source Shortest Paths Algorithm

Sebastian Forster (Speaker)

9 Oct 2018

Activity: Talk or presentationOral presentationscience to science / art to art

Annual European Symposium on Algorithms (Event)

Sebastian Forster (Member)

15 Apr 201824 Aug 2018

Activity: MembershipMembership of committee

Towards Optimal Dynamic Graph Compression

Sebastian Krinninger (Invited speaker)

15 Jun 2018

Activity: Talk or presentationOral presentationscience to science / art to art