Patrick Schnider
@schnpatr.bsky.social
Mathematician/Computer Scientist interested in discrete and computational geometry and topology. Working at University of Basel and ETH Zürich.
https://people.inf.ethz.ch/schnpatr/
https://people.inf.ethz.ch/schnpatr/
Reposted by Patrick Schnider
Both low-level implementation and analysis were previously very involved.
But our new paper simplifies both significantly.
Now
- Pretty readable for non-experts.
- Simple enough to code up fully in C++
- I am trying to teach it this semester arxiv.org/abs/2510.17182
2/3
But our new paper simplifies both significantly.
Now
- Pretty readable for non-experts.
- Simple enough to code up fully in C++
- I am trying to teach it this semester arxiv.org/abs/2510.17182
2/3
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots,U\}$ in $\tilde{O}(n^{2}\log U)$ time, which is near-optima...
arxiv.org
October 23, 2025 at 4:47 AM
Both low-level implementation and analysis were previously very involved.
But our new paper simplifies both significantly.
Now
- Pretty readable for non-experts.
- Simple enough to code up fully in C++
- I am trying to teach it this semester arxiv.org/abs/2510.17182
2/3
But our new paper simplifies both significantly.
Now
- Pretty readable for non-experts.
- Simple enough to code up fully in C++
- I am trying to teach it this semester arxiv.org/abs/2510.17182
2/3
Congratulations! 🥳
August 21, 2025 at 10:40 AM
Congratulations! 🥳
The Dowker complex has a beautiful duality: taking it on a set X relative to a set Y is homotopy equivalent to the complex on Y relative to X. While this does not hold for the Dowker-Rips complex, we show that in dimensions 0 and 1 you still get isomorphic homologies, even in the persistent setting.
August 12, 2025 at 5:49 AM
The Dowker complex has a beautiful duality: taking it on a set X relative to a set Y is homotopy equivalent to the complex on Y relative to X. While this does not hold for the Dowker-Rips complex, we show that in dimensions 0 and 1 you still get isomorphic homologies, even in the persistent setting.
While the Cech complex is often replaced by the Vietoris-Rips complex in practice, an analogous construction for the Dowker complex seems not to have been studied so far. We close this gap by introducing the Dowker-Rips complex.
August 12, 2025 at 5:48 AM
While the Cech complex is often replaced by the Vietoris-Rips complex in practice, an analogous construction for the Dowker complex seems not to have been studied so far. We close this gap by introducing the Dowker-Rips complex.
The Dowker complex is a simplicial complex used in #TDA to analyze the interplay between two data sets. Unfortunately, like the Cech complex, it is expensive to compute.
August 12, 2025 at 5:47 AM
The Dowker complex is a simplicial complex used in #TDA to analyze the interplay between two data sets. Unfortunately, like the Cech complex, it is expensive to compute.
Congratulations! 🥳
July 9, 2025 at 12:52 PM
Congratulations! 🥳
Now the rejections are out as well 😝
July 8, 2025 at 6:46 PM
Now the rejections are out as well 😝