4 Search Results for "Natarajan, Vijay"

Document
DOI: 10.4230/DagRep.13.5.71
Topological Data Analysis and Applications (Dagstuhl Seminar 23192)

Authors: Ulrich Bauer, Vijay Natarajan, and Bei Wang

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23192 "Topological Data Analysis and Applications". The seminar brought together researchers with backgrounds in mathematics, computer science, and different application domains with the aim of identifying and exploring emerging directions within computational topology for data analysis. This seminar was designed to be a followup event to two successful Dagstuhl Seminars (17292, July 2017; 19212, May 2019). The list of topics and participants were updated to reflect recent developments and to engage wider participation. Close interaction between the participants during the seminar accelerated the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis, and the identification of different applications of topological analysis.
Cite as

Ulrich Bauer, Vijay Natarajan, and Bei Wang. Topological Data Analysis and Applications (Dagstuhl Seminar 23192). In Dagstuhl Reports, Volume 13, Issue 5, pp. 71-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bauer_et_al:DagRep.13.5.71,
  author =	{Bauer, Ulrich and Natarajan, Vijay and Wang, Bei},
  title =	{{Topological Data Analysis and Applications (Dagstuhl Seminar 23192)}},
  pages =	{71--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Bauer, Ulrich and Natarajan, Vijay and Wang, Bei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.5.71},
  URN =		{urn:nbn:de:0030-drops-193652},
  doi =		{10.4230/DagRep.13.5.71},
  annote =	{Keywords: algorithms, applications, computational topology, topological data analysis, visualization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.13
On Computing Homological Hitting Sets

Authors: Ulrich Bauer, Abhishek Rathod, and Meirav Zehavi

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Cut problems form one of the most fundamental classes of problems in algorithmic graph theory. In this paper, we initiate the algorithmic study of a high-dimensional cut problem. The problem we study, namely, Homological Hitting Set (HHS), is defined as follows: Given a nontrivial r-cycle z in a simplicial complex, find a set 𝒮 of r-dimensional simplices of minimum cardinality so that 𝒮 meets every cycle homologous to z. Our first result is that HHS admits a polynomial-time solution on triangulations of closed surfaces. Interestingly, the minimal solution is given in terms of the cocycles of the surface. Next, we provide an example of a 2-complex for which the (unique) minimal hitting set is not a cocycle. Furthermore, for general complexes, we show that HHS is W[1]-hard with respect to the solution size p. In contrast, on the positive side, we show that HHS admits an FPT algorithm with respect to p+Δ, where Δ is the maximum degree of the Hasse graph of the complex 𝖪.
Cite as

Ulrich Bauer, Abhishek Rathod, and Meirav Zehavi. On Computing Homological Hitting Sets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.ITCS.2023.13,
  author =	{Bauer, Ulrich and Rathod, Abhishek and Zehavi, Meirav},
  title =	{{On Computing Homological Hitting Sets}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.13},
  URN =		{urn:nbn:de:0030-drops-175169},
  doi =		{10.4230/LIPIcs.ITCS.2023.13},
  annote =	{Keywords: Algorithmic topology, Cut problems, Surfaces, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.17
Parallel Computation of Alpha Complexes for Biomolecules

Authors: Talha Bin Masood, Tathagata Ray, and Vijay Natarajan

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

Abstract
The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are optimized for biomolecules.
Cite as

Talha Bin Masood, Tathagata Ray, and Vijay Natarajan. Parallel Computation of Alpha Complexes for Biomolecules. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{masood_et_al:LIPIcs.SoCG.2020.17,
  author =	{Masood, Talha Bin and Ray, Tathagata and Natarajan, Vijay},
  title =	{{Parallel Computation of Alpha Complexes for Biomolecules}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{17:1--17:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.17},
  URN =		{urn:nbn:de:0030-drops-121758},
  doi =		{10.4230/LIPIcs.SoCG.2020.17},
  annote =	{Keywords: Delaunay triangulation, parallel algorithms, biomolecules, GPU}
}
Document
DOI: 10.4230/DagRep.9.5.110
Topology, Computation and Data Analysis (Dagstuhl Seminar 19212)

Authors: Michael Kerber, Vijay Natarajan, and Bei Wang

Published in: Dagstuhl Reports, Volume 9, Issue 5 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19212 "Topology, Computation and Data Analysis". The seminar brought together researchers with mathematical and computational backgrounds in addressing emerging directions within computational topology for data analysis in practice. This seminar was designed to be a followup event after a very successful Dagstuhl Seminar (17292; July 2017). The list of topics and participants were updated to keep the discussions diverse, refreshing, and engaging. This seminar facilitated close interactions among the attendees with the aim of accelerating the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis.
Cite as

Michael Kerber, Vijay Natarajan, and Bei Wang. Topology, Computation and Data Analysis (Dagstuhl Seminar 19212). In Dagstuhl Reports, Volume 9, Issue 5, pp. 110-131, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{kerber_et_al:DagRep.9.5.110,
  author =	{Kerber, Michael and Natarajan, Vijay and Wang, Bei},
  title =	{{Topology, Computation and Data Analysis (Dagstuhl Seminar 19212)}},
  pages =	{110--131},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{5},
  editor =	{Kerber, Michael and Natarajan, Vijay and Wang, Bei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.5.110},
  URN =		{urn:nbn:de:0030-drops-113832},
  doi =		{10.4230/DagRep.9.5.110},
  annote =	{Keywords: computational topology, topological data analysis, Topology based visualization}
}
  • Refine by Author
  • 3 Natarajan, Vijay
  • 2 Bauer, Ulrich
  • 2 Wang, Bei
  • 1 Kerber, Michael
  • 1 Masood, Talha Bin
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Algebraic topology
  • 2 Theory of computation → Computational geometry
  • 1 Applied computing → Molecular structural biology
  • 1 Computing methodologies → Shape modeling
  • 1 Human-centered computing → Visualization
  • Show More...

  • Refine by Keyword
  • 2 computational topology
  • 2 topological data analysis
  • 1 Algorithmic topology
  • 1 Cut problems
  • 1 Delaunay triangulation
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2023
  • 1 2019
  • 1 2020

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 Imprint Privacy Contact