Picture of Simon Meierhans in Italy

About

I am a computer science PhD student in the group of Rasmus Kyng at the Department of Computer Science, ETH Zurich.

My research is supported by the 2024 Google PhD Fellowship.

My interests lie in the realm of algorithms and optimization. In particular, I am fascinated by fast graph algorithms and their relations to linear algebra. I occasionally dabble in other fields, such as deep learning and high performance computing, and I have very broad interests.

Recently, my work has led to almost optimal minimum-cost flow algorithms for 'partially dynamic' graphs. These algorithms generalize minimum-cost flow algorithms to networks that either only increase or only decrease in connectivity, and resolve many core problems on partially dynamic graphs via direct reductions. Notably, our result for decreasing connectivity achieves the best known time bounds even for static graphs. You can read about this line of work in the Simons Institute Newsletter by Nikhil Srivastava and in an accessible article featured in the ETH news, or watch me give a technical talk about it. See also publications below.

In Fall 2023 I was a visitor at the Data Structures and Optimization for Fast Algorithms program at the Simons Institute in Berkeley, California.

I was awarded the ETH Medal for my Master Thesis on Incremental Single Source Shortest Paths supervised by Maximilian Probst Gutenberg and Rasmus Kyng.

Publications

I maintain a Google Scholar profile listing the articles I contributed to. The ones made available on arXiv are openly accessible.

  • Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
    with Daoyuan Chen, Maximilian Probst Gutenberg and Thatchaphol Saranurak
    [arXiv][to appear at SODA'25]
  • A Simple Dynamic Spanner via APSP
    with Rasmus Kyng and Gernot Zöcklein
    [arXiv]
  • Bootstrapping Dynamic APSP via Sparsification
    with Rasmus Kyng and Gernot Zöcklein
    [arXiv]
  • Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
    with Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg and Sushant Sachdeva
    [arXiv][to appear at FOCS'24]
  • Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Maximum & Minimum-Cost Flow
    with Li Chen, Rasmus Kyng, Yang P. Liu and Maximilian Probst Gutenberg
    [arXiv][STOC'24]
    Featured in Simons Institute Newsletter by Nikhil Srivastava.
  • A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
    with Rasmus Kyng and Maximilian Probst Gutenberg
    [arXiv][STOC'24]
  • Derandomizing Directed Random Walks in Almost-Linear Time
    with Rasmus Kyng and Maximilian Probst Gutenberg
    [arXiv][FOCS'22]
  • Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
    with Rasmus Kyng and Maximilian Probst Gutenberg
    [arXiv][SODA'22]
  • Content adaptive optimization for neural image compression
    with Joaquim Campos, Abdelaziz Djelouah and Christopher Schroers
    [arXiv] [CVPR Workshop and Challenge on Learned Image Compression'19]
    Joaquim features an accessible and elegant exposition of this result and related work on his website.
  • Resilient Dictionaries for Randomly Unreliable Memory
    with Stefano Leucci and Chih-Hung Liu
    [ESA'19]
  • Transformations of high-level synthesis codes for high-performance computing
    with Johannnes de Fine Licht, Maciej Besta and Torsten Hoefler
    [arXiv][TPDS][code]

Talks

  • Almost-Linear Time Algorithms for Partially Dynamic Graphs
    Google Research, Zürich, Switzerland
  • Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
    FOCS'24, Chicago, IL, USA
  • Almost-Linear Time Algorithms for Partially Dynamic Graphs
    Brown Theory Seminar, Brown University, Providence, RI, USA
  • Almost-Linear Time Algorithms for Partially Dynamic Graphs
    Algorithms and Complexity Seminar, MIT, Boston, MA, USA
  • Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
    STOC'24, Vancouver, BC, Canada
  • A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
    STOC'24, Vancouver, BC, Canada
  • Algorithms for Incremental Graphs via Fully Dynamic Min-Ratio Cycle (Poster)
    Jane Street, New York, NY, USA
  • Incremental Cycle Detection via Dynamic Minimum Cost Flow
    Algorithms Seminar, UC Berkeley, Berkeley, CA, USA
  • Incremental Cycle Detection via Dynamic Minimum Cost Flow
    Stanford Theory Lunch, Stanford, Palo Alto, CA, USA
  • Incremental Cycle Detection via Dynamic Minimum Cost Flow
    Google Research, Mountain View, CA, USA
  • Incremental Cycle Detection via Dynamic Minimum Cost Flow
    ETH Mittagsseminar, Zurich, Switzerland
  • Partial Symmetrization for Eulerian Laplacians
    Informal Blackboard Talk at Simons Institute for the Theory of Computing, Berkeley, CA, USA
  • Derandomizing Directed Random Walks in Almost-Linear Time
    FOCS'22, Denver, CO, USA
  • Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
    SODA'22, online
  • Resilient Dictionaries for Randomly Unreliable Memory
    ESA'19, Munich, Germany

Contact

You can reach me by email at:

  • firstname.lastname@inf.ethz.ch