Search Results

Documents authored by Pritam, Siddharth

Document
DOI: 10.4230/LIPIcs.SoCG.2024.21
On Edge Collapse of Random Simplicial Complexes

Authors: Jean-Daniel Boissonnat, Kunal Dutta, Soumik Dutta, and Siddharth Pritam

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We consider the edge collapse (introduced in [Boissonnat, Pritam. SoCG 2020]) process on the Erdős-Rényi random clique complex X(n,c/√n) on n vertices with edge probability c/√n such that c > √η₂ where η₂ = inf{η | x = e^{-η(1-x)²} has a solution in (0,1)}. For a given c > √η₂, we show that after t iterations of maximal edge collapsing phases, the remaining subcomplex, or t-core, has at most (1+o(1))binom(n,2)p(1-(c²/3)(1-(1-γ_t)³)) and at least (1+o(1)) binom(n,2) p(1-γ_{t+1}-c²γ_t(1-γ_t)²) edges asymptotically almost surely (a.a.s.), where {γ_t}_{t ≥ 0} is recursively determined by γ_{t+1} = e^{-c²(1-γ_t)²} and γ_0 = 0. We also determine the upper and lower bound on the final core with explicit formulas. If c < √{η₂} then we show that the final core contains o(n√n) edges. On the other hand, if, instead of c being a constant with respect to n, c > √{2log n} then the edge collapse process is no more effective in reducing the size of the complex. Our proof is based on the notion of local weak convergence [Aldous, Steele. In Probability on discrete structures. Springer, 2004] together with two new components. Firstly, we identify the critical combinatorial structures that control the outcome of the edge collapse process. By controlling the expected number of these structures during the edge collapse process we establish a.a.s. bounds on the size of the core. We also give a new concentration inequality for typically Lipschitz functions on random graphs which improves on the bound of [Warnke. Combinatorics, Probability and Computing, 2016] and is, therefore, of independent interest. The proof of our lower bound is via the recursive technique of [Linial and Peled. A Journey Through Discrete Mathematics. 2017] to simulate cycles in infinite trees. These are the first theoretical results proved for edge collapses on random (or non-random) simplicial complexes.
Cite as

Jean-Daniel Boissonnat, Kunal Dutta, Soumik Dutta, and Siddharth Pritam. On Edge Collapse of Random Simplicial Complexes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2024.21,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal and Dutta, Soumik and Pritam, Siddharth},
  title =	{{On Edge Collapse of Random Simplicial Complexes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.21},
  URN =		{urn:nbn:de:0030-drops-199661},
  doi =		{10.4230/LIPIcs.SoCG.2024.21},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Simple Collapse, Persistent homology, Random simplicial complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.44
Swap, Shift and Trim to Edge Collapse a Filtration

Authors: Marc Glisse and Siddharth Pritam

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit the use of edge collapse for efficient computation of persistent homology. We first give a simple and intuitive explanation of the principles underlying that algorithm. This in turn allows us to propose various extensions including a zigzag filtration simplification algorithm. We finally show some experiments to better understand how it behaves.
Cite as

Marc Glisse and Siddharth Pritam. Swap, Shift and Trim to Edge Collapse a Filtration. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{glisse_et_al:LIPIcs.SoCG.2022.44,
  author =	{Glisse, Marc and Pritam, Siddharth},
  title =	{{Swap, Shift and Trim to Edge Collapse a Filtration}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.44},
  URN =		{urn:nbn:de:0030-drops-160525},
  doi =		{10.4230/LIPIcs.SoCG.2022.44},
  annote =	{Keywords: edge collapse, flag complex, graph, persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.19
Edge Collapse and Persistence of Flag Complexes

Authors: Jean-Daniel Boissonnat and Siddharth Pritam

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appears to be a very powerful concept, especially when applied to flag complexes. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude w.r.t the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.
Cite as

Jean-Daniel Boissonnat and Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2020.19,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth},
  title =	{{Edge Collapse and Persistence of Flag Complexes}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.19},
  URN =		{urn:nbn:de:0030-drops-121777},
  doi =		{10.4230/LIPIcs.SoCG.2020.19},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.55
Computing Persistent Homology of Flag Complexes via Strong Collapses

Authors: Jean-Daniel Boissonnat and Siddharth Pritam

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.
Cite as

Jean-Daniel Boissonnat and Siddharth Pritam. Computing Persistent Homology of Flag Complexes via Strong Collapses. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.SoCG.2019.55,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth},
  title =	{{Computing Persistent Homology of Flag Complexes via Strong Collapses}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.55},
  URN =		{urn:nbn:de:0030-drops-104596},
  doi =		{10.4230/LIPIcs.SoCG.2019.55},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.67
Strong Collapse for Persistence

Authors: Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We introduce a fast and memory efficient approach to compute the persistent homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexes of the input sequence by using strong collapses, as introduced by J. Barmak and E. Miniam [DCG (2012)], and to compute the PH of an induced sequence of reduced simplicial complexes that has the same PH as the initial one. Our approach has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of all its simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel. As a result and as demonstrated by numerous experiments on publicly available data sets, our approach is extremely fast and memory efficient in practice.
Cite as

Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek. Strong Collapse for Persistence. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 67:1-67:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2018.67,
  author =	{Boissonnat, Jean-Daniel and Pritam, Siddharth and Pareek, Divyansh},
  title =	{{Strong Collapse for Persistence}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{67:1--67:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.67},
  URN =		{urn:nbn:de:0030-drops-95302},
  doi =		{10.4230/LIPIcs.ESA.2018.67},
  annote =	{Keywords: Computational Topology, Topological Data Analysis, Strong Collapse, Persistent homology}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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