Joakim Blikstad

I am a final-year PhD student at KTH Royal Institute of Technology, fortunate to be advised by Prof. Danupon Nanongkai. Previously, I did my undergrad at University of Waterloo.

I am often a long-term visitor at the Max Planck Institute for Informatics.

I am primarily interested in combinatorial optimization topics such as matching, maxflow, matroid intersection, and related graph problems. I like to study these problems in many models of computations simultaneously, such as dynamic, communication, parallel, and distributed models.

In my free time one can often find me sailing, skiing, hiking, or playing the piano.

Email: (lastname)@kth.se

News

• I will be defending my Ph.D. November 27, 2024. [thesis]
• Deterministic Online Bipartite Edge Coloring accepted at SODA'25 and Implementing Auction Algorithm For Efficient Matroid Intersection accepted at SOSA'25.
• Paper accepted at FOCS'24: Maximum Flow by Augmenting Paths in n^2+o(1) Time.
• As a jury member, I am helping to organize the European Girls' Olympiad in Informatics 2024 in the Netherlands, July 2024.
• Invited online talk Online Edge Coloring is (Nearly) as Easy as Offline at the Toyota Technological Institute at Chicago (TTIC) [slides] [recording] (May 2024).
• Two papers accepted to STOC'24: Online Edge Coloring is (Nearly) as Easy as Offline and Minimum Star Partitions of Simple Polygons in Polynomial Time.
• Recipient of a Google PhD Fellowship 2023.
• Paper accepted to SOSA'24: Simple and Asymptotically Optimal Online Bipartite Edge Coloring.
• Awarded best student paper at ESA'23: Incremental (1−ε)-approximate dynamic matching in O(poly(1/ε)) update time.

Publications

See also: [dblp] [Google Scholar]

1. Deterministic Online Bipartite Edge Coloring
   Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc.
   SODA 2025
   [arxiv]
2. Implementing Auction Algorithm For Efficient Matroid Intersection
   Joakim Blikstad, Ta-Wei Tu.
   SOSA 2025
   [arxiv]
3. Maximum Flow by Augmenting Paths in n^2+o(1) Time
   Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu.
   FOCS 2024 (invited to special issue)
   [arxiv] [slides]
4. Online Edge Coloring is (Nearly) as Easy as Offline
   Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc.
   STOC 2024 (invited to special issue)
   [arxiv] [proceedings] [slides] [talk@TTIC] [talk@STOC by R.V.]
5. Minimum Star Partitions of Simple Polygons in Polynomial Time
   Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang.
   STOC 2024
   [arxiv] [proceedings] [slides] [talk@STOC by H.Z.]
6. Simple and Asymptotically Optimal Online Bipartite Edge Coloring
   Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc.
   SOSA 2024
   [arxiv] [proceedings]
7. Incremental (1−ε)-approximate dynamic matching in O(poly(1/ε)) update time
   Joakim Blikstad, Peter Kiss.
   ESA 2023 Best Student Paper Award
   [arxiv] [proceedings] [slides]
8. Fast Algorithms via Dynamic-Oracle Matroids
   Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu.
   STOC 2023
   [arxiv] [proceedings] [slides] [talk@ETH] [talk@STOC by T.T.]
9. Nearly Optimal Communication and Query Complexity of Bipartite Matching
   Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai.
   FOCS 2022
   [arxiv] [proceedings] [slides] [talk@TCS+] [talk@IAS by Y.E.]
10. Sublinear-round Parallel Matroid Intersection
    Joakim Blikstad.
    ICALP 2022 Best Student Paper Award
    [proceedings] [slides]
11. Breaking O(nr) for Matroid Intersection
    Joakim Blikstad.
    ICALP 2021
    [arxiv] [proceedings] [slides]
12. Breaking the Quadratic Barrier for Matroid Intersection
    Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai.
    STOC 2021
    [arxiv] [proceedings] [slides] [talk@STOC]
13. On the longest common subsequence of Thue-Morse words
    Joakim Blikstad.
    Information Processing Letters (2020)
    [arxiv] [journal]