Patrick Schnider

My Research

For a list of my publications, visit my profiles on Google Scholar and dblp.

Topological Data Analysis

Topological data analysis is a relatively young subfield of data science which uses ideas and methods from algebraic topology to study the shape of data. Despite only having been introduced a bit more than 20 years ago, topological data analysis has already found many applications. From a mathematicians perspective, I also appreciate the beautiful mathematics that lie at the core of the theory. In my research I am particularly interested in the stability and robustness of persistent homology and the Mapper algorithm, and in my work I try to apply concepts from discrete geometry to the pipeline of topological data analysis. For more background, I have also written some lecture notes.

Depth Measures for high-dimensional data

Depth measures are a way to generalize the concept of a median to higher dimensions. Several different depth measures have been introduced in the literature, all of which lead to interesting combinatorial and computational questions. I am particularly interested in the relationship between different measures and the depth structures that they induce on a data set in high dimensions.

Topological Methods in Discrete Geometry

The well-known Ham-Sandwich Theorem states that any d masses in d-dimensional space can be simultaneously bisected by a single hyperplane. The proof of this result uses tools from algebraic topology, namely the famous Borsuk-Ulam Theorem. A natural question now is to ask, whether we can bisect even more masses, if we use more or different types of cuts. For many such questions, new topological tools, similar to the Borsuk-Ulam Theorem, are required.

Some selected papers

Here you find a selection of some of my recent papers.

Enclosing Depth and other Depth MeasuresCombinatorica 2023

I study families of depth measures defined by natural sets of axioms. I show that any such depth measure is a constant factor approximation of Tukey depth. I further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy the most restrictive set of axioms, which includes Tukey depth. Along the way, I introduce and study a new depth measure called enclosing depth, which I believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.

Query-Efficient Fixpoints of lp-ContractionsFOCS 2025

We develop a query-efficient algorithm to find an approximate fixpoint of a map that is contracting under an lp-norm. Previously, such algorithms were only known for the l-infinity metric. To prove our results, we introduce the notion of lp-halfspaces and generalize the classical centerpoint theorem from discrete geometry. The proof of this generalized centerpoint theorem uses topological methods, namely Brouwer's fixpoint theorem.

A Topological Version of Schaefer's Dichotomy TheoremSoCG 2024

Schaefer's dichotomy theorem states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for every type of constraint allowed in its instances. Otherwise, it is NP-complete. In this paper, together with Simon Weber we analyze boolean CSPs in terms of their topological complexity, instead of their computational complexity. We attach a natural topological space to the set of solutions of a boolean CSP and introduce the notion of projection-universality. We prove that a boolean CSP is projection-universal if and only if it is categorized as NP-complete by Schaefer's dichotomy theorem, showing that the dichotomy translates exactly from computational to topological complexity. We show a similar dichotomy for SAT variants and homotopy-universality.

Home / Research