40 Search Results for "Bauer, Ulrich"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.6
Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations

Authors: Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Given an unknown ℝⁿ-valued function f on a metric space X, can we approximate the persistent homology of f from a finite sampling of X with known pairwise distances and function values? This question has been answered in the case n = 1, assuming f is Lipschitz continuous and X is a sufficiently regular geodesic metric space, and using filtered geometric complexes with fixed scale parameter for the approximation. In this paper we answer the question for arbitrary n, under similar assumptions and using function-geometric multifiltrations. Our analysis offers a different view on these multifiltrations by focusing on their approximation properties rather than on their stability properties. We also leverage the multiparameter setting to provide insight into the influence of the scale parameter, whose choice is central to this type of approach. From a practical standpoint, we show that our approximation results are robust to input noise, and that function-geometric multifiltrations have good statistical convergence properties. We also provide an algorithm to compute our estimators, and we use its implementation to conduct extensive experiments, on both synthetic and real biological data, in order to validate our theoretical results.
Cite as

Ethan André, Jingyi Li, David Loiseaux, and Steve Oudot. Estimating the Persistent Homology of ℝⁿ-Valued Functions Using Function-Geometric Multifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andre_et_al:LIPIcs.SoCG.2026.6,
  author =	{Andr\'{e}, Ethan and Li, Jingyi and Loiseaux, David and Oudot, Steve},
  title =	{{Estimating the Persistent Homology of \mathbb{R}ⁿ-Valued Functions Using Function-Geometric Multifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.6},
  URN =		{urn:nbn:de:0030-drops-258120},
  doi =		{10.4230/LIPIcs.SoCG.2026.6},
  annote =	{Keywords: Topological data analysis, multi-parameter persistent homology, function-Rips multifiltration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.41
The Depth Poset Under Transpositions in the Filter

Authors: Herbert Edelsbrunner, Michał Lipiński, Marian Mrozek, Manuel Soriano-Trigueros, and Fedor Zimin

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies.
Cite as

Herbert Edelsbrunner, Michał Lipiński, Marian Mrozek, Manuel Soriano-Trigueros, and Fedor Zimin. The Depth Poset Under Transpositions in the Filter. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2026.41,
  author =	{Edelsbrunner, Herbert and Lipi\'{n}ski, Micha{\l} and Mrozek, Marian and Soriano-Trigueros, Manuel and Zimin, Fedor},
  title =	{{The Depth Poset Under Transpositions in the Filter}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{41:1--41:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.41},
  URN =		{urn:nbn:de:0030-drops-258479},
  doi =		{10.4230/LIPIcs.SoCG.2026.41},
  annote =	{Keywords: Algebraic topology, Lefschetz complexes, persistent homology, vines and vineyards, birth-death pairs, shallow pairs, relations, partial orders, transpositions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.47
Computing the Skyscraper Invariant

Authors: Marc Fersztand and Jan Jendrysiak

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We develop the first algorithms for computing the Skyscraper Invariant [FJNT24]. This is a filtration of the classical rank invariant for multiparameter persistence modules defined by the Harder-Narasimhan filtrations along every central charge supported at a single parameter value. Cheng’s algorithm [Cheng24] can be used to compute HN filtrations of arbitrary acyclic quiver representations in polynomial time in the total dimension, but in practice, the large dimension of persistence modules makes this direct approach infeasible. We show that by exploiting the additivity of the HN filtration and the special central charges, one can get away with a brute-force approach. For d-parameter modules, this produces an FPT ε-approximate algorithm with runtime dominated by 𝒪(1/ε^d ⋅ T_dec), where T_dec is the time for decomposition, which we compute with aida [DJK25]. We show that the wall-and-chamber structure of the module can be computed via lower envelopes of degree d - 1 polynomials. This allows for an exact computation of the Skyscraper Invariant roughly in 𝒪(n^d ⋅ T_dec) time for n the size of the presentation and enables a fast hybrid algorithm. For 2-parameter modules, we have implemented not only our algorithms but also, for the first time, Cheng’s algorithm. We compare all algorithms and, as a proof of concept for data analysis, compute a filtered version of the Multiparameter Landscape for biomedical data.
Cite as

Marc Fersztand and Jan Jendrysiak. Computing the Skyscraper Invariant. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fersztand_et_al:LIPIcs.SoCG.2026.47,
  author =	{Fersztand, Marc and Jendrysiak, Jan},
  title =	{{Computing the Skyscraper Invariant}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{47:1--47:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.47},
  URN =		{urn:nbn:de:0030-drops-258535},
  doi =		{10.4230/LIPIcs.SoCG.2026.47},
  annote =	{Keywords: Topological Data Analysis, Multiparameter Persistence, Persistence, Harder-Narasimhan Filtration, Skyscraper Invariant}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.72
Topological Simplification Guided by Forbidden Regions

Authors: Jakub Leśkiewicz, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Topological simplification is the process of reducing complexity of a function while maintaining its essential features. Its goal is to find a new filter function, which reorders cells of the input complex in a way which eliminates some persistent homological features, without affecting the rest. We present a new approach to simplification based on the concept of forbidden regions and combinatorial dynamics. It allows us to reorder and cancel critical values, whose cancellation is not possible using existing methods because they are not consecutive in the total order. Each such cancellation takes O(c⋅n) time in the worst case, where c is the number of birth-death pairs and n is the size of the input complex.
Cite as

Jakub Leśkiewicz, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov. Topological Simplification Guided by Forbidden Regions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{leskiewicz_et_al:LIPIcs.SoCG.2026.72,
  author =	{Le\'{s}kiewicz, Jakub and Furmanek, Bartosz and Lipi\'{n}ski, Micha{\l} and Morozov, Dmitriy},
  title =	{{Topological Simplification Guided by Forbidden Regions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{72:1--72:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.72},
  URN =		{urn:nbn:de:0030-drops-258797},
  doi =		{10.4230/LIPIcs.SoCG.2026.72},
  annote =	{Keywords: persistent homology, topological simplification, depth posets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.79
D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence

Authors: Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
End-to-end topological learning using 1-parameter persistence is well-known. We show that the framework can be enhanced using 2-parameter persistence by adopting a recently introduced 2-parameter persistence based vectorization technique called Gril. We establish a theory for gradient descent on Gril producing D-Gril. We show that D-Gril can be used to learn a bifiltration function on benchmark graph datasets. Further, we exhibit that this framework can be applied in the context of bio-activity prediction in drug discovery.
Cite as

Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey. D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 79:1-79:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.SoCG.2026.79,
  author =	{Mukherjee, Soham and Samaga, Shreyas N. and Xin, Cheng and Oudot, Steve and Dey, Tamal K.},
  title =	{{D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{79:1--79:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.79},
  URN =		{urn:nbn:de:0030-drops-258865},
  doi =		{10.4230/LIPIcs.SoCG.2026.79},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Multiparameter Persistence, Graph Learning, Graph Neural Networks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.85
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes

Authors: Geevarghese Philip and Erlend Raa Vågset

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has been studied extensively in heuristic, approximation, and parameterized complexity settings. Parameterized by treewidth k, OMM has long been known to be solvable on triangulations of 3-manifolds in 2^O(k²) n^O(1) time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on k has remained an open question. We resolve this by giving a new 2^O(k log k) n-time algorithm for any finite regular CW complex, and show that no 2^o(k log k) n^O(1)-time algorithm exists unless the Exponential Time Hypothesis (ETH) fails.
Cite as

Geevarghese Philip and Erlend Raa Vågset. ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 85:1-85:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{philip_et_al:LIPIcs.SoCG.2026.85,
  author =	{Philip, Geevarghese and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{85:1--85:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.85},
  URN =		{urn:nbn:de:0030-drops-258926},
  doi =		{10.4230/LIPIcs.SoCG.2026.85},
  annote =	{Keywords: Discrete Morse Theory, Simplicial Complexes, Optimal Morse Matching, Treewidth, Parameterized Algorithms, Computational Topology, Dynamic Programming, Exponential Time Hypothesis, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.87
Robustness of Persistent Topological Features and Minimum Homological Cuts

Authors: Pepijn Roos Hoefgeest and Lucas Slot

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Persistent homology is a popular method for computing topological features of (metric) data. Standard approaches based on the Čech or Rips filtration are stable under small perturbations of the data, but highly sensitive to outliers. This lack of robustness has been frequently addressed in the literature. In this paper, we take a novel perspective by asking the following question: When can we guarantee that an observed persistent feature (a bar) is inherent to the underlying data in the presence of a limited number of unknown, arbitrary outliers. We formalize this question by introducing the notion of adversarial robustness, and study the problem of deciding whether a given bar in the barcode of a filtered simplicial complex is adversarially robust. We show that this problem is essentially equivalent to a homological variant of the minimum cut problem in simplicial complexes, which we believe to be of independent interest. As our main technical contribution, we provide the first computational complexity results for this problem, consisting of an efficient algorithm in 0-dimensional homology, NP-hardness for the general problem, and an efficient algorithm for codimension-1 in n-dimensional complexes embedded in ℝⁿ. We also analyze its natural linear programming relaxation, whose dual defines a homological analog of the max-flow problem in graphs. We show that a max-flow/min-cut theorem does not hold in our setting, implying that the LP relaxation is not tight in general. Finally, in the special case of the Rips filtration, we provide a global heuristic based on the Hausdorff distance that guarantees adversarial robustness of sufficiently long bars. This connects adversarial robustness to standard stability theorems in persistent homology.
Cite as

Pepijn Roos Hoefgeest and Lucas Slot. Robustness of Persistent Topological Features and Minimum Homological Cuts. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2026.87,
  author =	{Roos Hoefgeest, Pepijn and Slot, Lucas},
  title =	{{Robustness of Persistent Topological Features and Minimum Homological Cuts}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{87:1--87:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.87},
  URN =		{urn:nbn:de:0030-drops-258636},
  doi =		{10.4230/LIPIcs.SoCG.2026.87},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Min-cut Max-flow, Robustness, Vietoris-Rips Filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.94
Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds

Authors: Hubert Wagner, Nickolas Arustamyan, Matthew Wheeler, and Peter Bubenik

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We propose a novel geometric-topological descriptor called a mixup barcode. Intuitively, it characterizes the shape of a point cloud as well as its spatial relationship with another point cloud embedded in the same ambient space. More technically, it enriches a standard persistence barcode with information on the image persistent homology. In three dimensions it captures natural spatial relationships like overlap and surrounding; in higher dimensions more intricate spatial relationships are captured. We provide a theoretical setup and a simple algorithm for mixup barcodes. As a proof of concept, we explore data arising in a geometric-topological problem from machine learning. Specifically, we take first steps towards verifying a hypothesis stating that geometric-topological relationships within intermediate point cloud representations in an artificial neural network can hinder its training. More broadly, our experiments suggest that mixup barcodes are useful for characterizing spatial relationships and spatial interactions (i.e. the evolution of spatial relationships) that are hard to directly visualize or capture using standard methods.
Cite as

Hubert Wagner, Nickolas Arustamyan, Matthew Wheeler, and Peter Bubenik. Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 94:1-94:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.SoCG.2026.94,
  author =	{Wagner, Hubert and Arustamyan, Nickolas and Wheeler, Matthew and Bubenik, Peter},
  title =	{{Mixup Barcodes: Quantifying Geometric-Topological Interactions Between Point Clouds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{94:1--94:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.94},
  URN =		{urn:nbn:de:0030-drops-259009},
  doi =		{10.4230/LIPIcs.SoCG.2026.94},
  annote =	{Keywords: mixup barcode, persistent homology, persistence barcode, persistence diagram, image persistent homology, image persistence, deep learning, multilayer perceptron, topology of neural network embeddings, disentanglement}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.5
Bifunction and Interlevel Delaunay Trifiltrations

Authors: Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an ℝ-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an ℝ²-valued function, also satisfying an analogous weak equivalence. For a point cloud X ⊂ ℝ^d, our trifiltration has size O(|X|^{⌈(d+1)/2⌉+1}). We present an algorithm that computes this trifiltration in time O(|X|^{⌈d/2⌉+2}), together with an implementation. Our experiments demonstrate that the implementation can handle thousands of points in ℝ³, with memory growth that is nearly linear.
Cite as

Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick, and Abhishek Rathod. Bifunction and Interlevel Delaunay Trifiltrations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alonso_et_al:LIPIcs.SoCG.2026.5,
  author =	{Alonso, \'{A}ngel Javier and Kerber, Michael and Lam, Tung and Lesnick, Michael and Rathod, Abhishek},
  title =	{{Bifunction and Interlevel Delaunay Trifiltrations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.5},
  URN =		{urn:nbn:de:0030-drops-258118},
  doi =		{10.4230/LIPIcs.SoCG.2026.5},
  annote =	{Keywords: Delaunay triangulation, Multiparameter persistent homology, Interlevel, Bowyer-Watson}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.10
Fast Free Resolutions of Bifiltered Chain Complexes

Authors: Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
In a k-critical bifiltration, every simplex enters along a staircase with at most k steps. Examples with k > 1 include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a k-critical bifiltration into a 1-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations. We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size. We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a k-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size.
Cite as

Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls. Fast Free Resolutions of Bifiltered Chain Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2026.10,
  author =	{Bauer, Ulrich and Dey, Tamal K. and Kerber, Michael and Russold, Florian and S\"{o}ls, Matthias},
  title =	{{Fast Free Resolutions of Bifiltered Chain Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.10},
  URN =		{urn:nbn:de:0030-drops-258161},
  doi =		{10.4230/LIPIcs.SoCG.2026.10},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Multi-Critical Bifiltrations}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.21
Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O

Authors: Amirmohammad Nazari, Rajit Manohar, and Robert Soulé

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
In this paper, we propose a novel software/hardware design to improve I/O performance while maintaining existing POSIX-standard APIs. Our approach stands in contrast to existing kernel-bypass strategies that improve performance at the expense of abandoning familiar programming abstractions. Our key insight is that navigating the performance-functionality trade-off requires changes to the processor; it cannot be done without support of the CPU micro-architecture. Our design, called Accio, includes: dedicated hardware for interrupt management, a hardware assist for thread scheduling, tables in hardware that manage I/O state, and modifications to the operating system to support the new hardware. Our evaluation demonstrates that Accio saturates the bus bandwidth, reduces CPU usage by up to 66% compared to state-of-the-art kernel-bypass systems, and reduces latency to 1/12th of that of the Linux kernel, matching that of kernel-bypass systems.
Cite as

Amirmohammad Nazari, Rajit Manohar, and Robert Soulé. Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nazari_et_al:OASIcs.NINeS.2026.21,
  author =	{Nazari, Amirmohammad and Manohar, Rajit and Soul\'{e}, Robert},
  title =	{{Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{21:1--21:24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.21},
  URN =		{urn:nbn:de:0030-drops-256063},
  doi =		{10.4230/OASIcs.NINeS.2026.21},
  annote =	{Keywords: Networks, Operating Systems, I/O Optimization}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.60
Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation

Authors: Yannic Maus and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We give new, improved bounds for approximating the sparsest cut value or in other words the conductance ϕ of a graph in the CONGEST model. As our main result, we present an algorithm running in O(log² n/ϕ) rounds in which every vertex outputs a value ̃ ϕ satisfying ϕ ≤ ̃ ϕ ≤ √{2.01ϕ}. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix L: = I-Deg^{-1/2}ADeg^ {-1/2}, where, A is the adjacency matrix and Deg is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.
Cite as

Yannic Maus and Tijn de Vos. Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maus_et_al:LIPIcs.DISC.2025.60,
  author =	{Maus, Yannic and de Vos, Tijn},
  title =	{{Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{60:1--60:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.60},
  URN =		{urn:nbn:de:0030-drops-248763},
  doi =		{10.4230/LIPIcs.DISC.2025.60},
  annote =	{Keywords: CONGEST, Sparsest Cut, Laplacian, Eigenvalues, Spectral Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.11
When Alpha-Complexes Collapse onto Codimension-1 Submanifolds

Authors: Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones.
Cite as

Dominique Attali, Mattéo Clémot, Bianca B. Dornelas, and André Lieutier. When Alpha-Complexes Collapse onto Codimension-1 Submanifolds. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2025.11,
  author =	{Attali, Dominique and Cl\'{e}mot, Matt\'{e}o and Dornelas, Bianca B. and Lieutier, Andr\'{e}},
  title =	{{When Alpha-Complexes Collapse onto Codimension-1 Submanifolds}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.11},
  URN =		{urn:nbn:de:0030-drops-231630},
  doi =		{10.4230/LIPIcs.SoCG.2025.11},
  annote =	{Keywords: Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.14
Extremal Betti Numbers and Persistence in Flag Complexes

Authors: Lies Beers and Magnus Bakke Botnan

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We investigate several problems concerning extremal Betti numbers and persistence in filtrations of flag complexes. For graphs on n vertices, we show that β_k(X(G)) is maximal when G = 𝒯_{n,k+1}, the Turán graph on k+1 partition classes, where X(G) denotes the flag complex of G. Building on this, we construct an edgewise (one edge at a time) filtration 𝒢 = G₁ ⊆ ⋯ ⊆ 𝒯_{n,k+1} for which β_k(X(G_i)) is maximal for all graphs on n vertices and i edges. Moreover, the persistence barcode ℬ_k(X(G)) achieves a maximal number of intervals, and total persistence, among all edgewise filtrations with |E(𝒯_{n,k+1})| edges. For k = 1, we consider edgewise filtrations of the complete graph K_n. We show that the maximal number of intervals in the persistence barcode is obtained precisely when G_{⌈n/2⌉ ⋅ ⌊n/2⌋} = 𝒯_{n,2}. Among such filtrations, we characterize those achieving maximal total persistence. We further show that no filtration can optimize β₁(X(G_i)) for all i, and conjecture that our filtrations maximize the total persistence over all edgewise filtrations of K_n.
Cite as

Lies Beers and Magnus Bakke Botnan. Extremal Betti Numbers and Persistence in Flag Complexes. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beers_et_al:LIPIcs.SoCG.2025.14,
  author =	{Beers, Lies and Bakke Botnan, Magnus},
  title =	{{Extremal Betti Numbers and Persistence in Flag Complexes}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.14},
  URN =		{urn:nbn:de:0030-drops-231668},
  doi =		{10.4230/LIPIcs.SoCG.2025.14},
  annote =	{Keywords: Topological data analysis, Extremal graph theory}
}
  • Refine by Type
  • 40 Document/PDF
  • 24 Document/HTML

  • Refine by Publication Year
  • 12 2026
  • 11 2025
  • 2 2024
  • 4 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 12 Bauer, Ulrich
  • 5 Dey, Tamal K.
  • 5 Rathod, Abhishek
  • 4 Morozov, Dmitriy
  • 3 Kerber, Michael
  • Show More...

  • Refine by Series/Journal
  • 35 LIPIcs
  • 3 OASIcs
  • 1 LITES
  • 1 DagRep

  • Refine by Classification
  • 24 Mathematics of computing → Algebraic topology
  • 19 Theory of computation → Computational geometry
  • 4 Computing methodologies → Algebraic algorithms
  • 4 Mathematics of computing → Geometric topology
  • 3 Mathematics of computing → Topology
  • Show More...

  • Refine by Keyword
  • 10 Topological Data Analysis
  • 7 persistent homology
  • 4 Persistent Homology
  • 3 Persistent homology
  • 3 image persistence
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact