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