Joakim Blikstad

I am excited to join Centrum Wiskunde & Informatica (CWI) in the Netherlands as a Postdoctoral Researcher. I recently completed my PhD at KTH Royal Institute of Technology under the supervision of Professor Danupon Nanongkai. Previously, I did my undergrad at University of Waterloo.

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

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

Email: (firstname)@cwi.nl

Office: Room M239, CWI Amsterdam, Science Park 123, 1098 XG Amsterdam, The Netherlands

News

• I defended my Ph.D. November 27, 2024! [thesis]
• Deterministic Online Bipartite Edge Coloring accepted at SODA'25 and Efficient Matroid Intersection via a Batch-Update Auction Algorithm 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] [proceedings]
2. Efficient Matroid Intersection via a Batch-Update Auction Algorithm
   Joakim Blikstad, Ta-Wei Tu.
   SOSA 2025
   [arxiv] [proceedings]
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] [proceedings] [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]