3 Search Results for "Lenzen, Fabian"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.37

Fast Approximate Counting of Cycles

Authors: Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal.

Cite as

Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia},
  title =	{{Fast Approximate Counting of Cycles}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.37},
  URN =		{urn:nbn:de:0030-drops-201809},
  doi =		{10.4230/LIPIcs.ICALP.2024.37},
  annote =	{Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.50

Cup Product Persistence and Its Efficient Computation

Authors: Tamal K. Dey and Abhishek Rathod

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

Abstract

It is well-known that the cohomology ring has a richer structure than homology groups. However, until recently, the use of cohomology in persistence setting has been limited to speeding up of barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an O(d n⁴) algorithm for computing the persistent k-cup modules for all k ∈ {2, … , d}, where d denotes the dimension of the filtered complex, and n denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it for d ≥ 3. Finally, we introduce a new stable invariant called partition modules of cup product that is more discriminative than persistent cup modules and devise an O(c(d)n⁴) algorithm for computing it, where c(d) is subexponential in d.

Cite as

Tamal K. Dey and Abhishek Rathod. Cup Product Persistence and Its Efficient Computation. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.50,
  author =	{Dey, Tamal K. and Rathod, Abhishek},
  title =	{{Cup Product Persistence and Its Efficient Computation}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{50:1--50:15},
  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.50},
  URN =		{urn:nbn:de:0030-drops-199958},
  doi =		{10.4230/LIPIcs.SoCG.2024.50},
  annote =	{Keywords: Persistent cohomology, cup product, image persistence, persistent cup module}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.15

Efficient Two-Parameter Persistence Computation via Cohomology

Authors: Ulrich Bauer, Fabian Lenzen, and Michael Lesnick

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

Clearing is a simple but effective optimization for the standard algorithm of persistent homology (ph), which dramatically improves the speed and scalability of ph computations for Vietoris-Rips filtrations. Due to the quick growth of the boundary matrices of a Vietoris-Rips filtration with increasing dimension, clearing is only effective when used in conjunction with a dual (cohomological) variant of the standard algorithm. This approach has not previously been applied successfully to the computation of two-parameter ph. We introduce a cohomological algorithm for computing minimal free resolutions of two-parameter ph that allows for clearing. To derive our algorithm, we extend the duality principles which underlie the one-parameter approach to the two-parameter setting. We provide an implementation and report experimental run times for function-Rips filtrations. Our method is faster than the current state-of-the-art by a factor of up to 20.

Cite as

Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient Two-Parameter Persistence Computation via Cohomology. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2023.15,
  author =	{Bauer, Ulrich and Lenzen, Fabian and Lesnick, Michael},
  title =	{{Efficient Two-Parameter Persistence Computation via Cohomology}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.15},
  URN =		{urn:nbn:de:0030-drops-178656},
  doi =		{10.4230/LIPIcs.SoCG.2023.15},
  annote =	{Keywords: Persistent homology, persistent cohomology, two-parameter persistence, clearing}
}

Refine by Author
1 Bauer, Ulrich
1 Censor-Hillel, Keren
1 Dey, Tamal K.
1 Even, Tomer
1 Lenzen, Fabian
Show More...

Refine by Classification
2 Mathematics of computing → Algebraic topology
2 Theory of computation → Computational geometry
1 Mathematics of computing → Approximation algorithms
1 Mathematics of computing → Graph algorithms

Refine by Keyword
1 Approximate cycle counting Fast matrix multiplication
1 Approximate triangle counting
1 Fast rectangular matrix multiplication
1 Persistent cohomology
1 Persistent homology
Show More...

Refine by Type
3 document

Refine by Publication Year
2 2024
1 2023