14 Search Results for "Wang, Bei"

Document
DOI: 10.4230/LIPIcs.DNA.30.1
Geometric Enumeration of Localized DNA Strand Displacement Reaction Networks

Authors: Matthew R. Lakin and Sarika Kumar

Published in: LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024)

Abstract
Localized molecular devices are a powerful tool for engineering complex information-processing circuits and molecular robots. Their practical advantages include speed and scalability of interactions between components tethered near to each other on an underlying nanostructure, and the ability to restrict interactions between more distant components. The latter is a critical feature that must be factored into computational tools for the design and simulation of localized molecular devices: unlike in solution-phase systems, the geometries of molecular interactions must be accounted for when attempting to determine the network of possible reactions in a tethered molecular system. This work aims to address that challenge by integrating, for the first time, automated approaches to analysis of molecular geometry with reaction enumeration algorithms for DNA strand displacement reaction networks that can be applied to tethered molecular systems. By adapting a simple approach to solving the biophysical constraints inherent in molecular interactions to be applicable to tethered systems, we produce a localized reaction enumeration system that enhances previous approaches to reaction enumeration in tethered system by not requiring users to explicitly specify the subsets of components that are capable of interacting. This greatly simplifies the user’s task and could also be used as the basis of future systems for automated placement or routing of signal-transmission and logical processing in molecular devices. We apply this system to several published example systems from the literature, including both tethered molecular logic systems and molecular robots.
Cite as

Matthew R. Lakin and Sarika Kumar. Geometric Enumeration of Localized DNA Strand Displacement Reaction Networks. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30). Leibniz International Proceedings in Informatics (LIPIcs), Volume 314, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lakin_et_al:LIPIcs.DNA.30.1,
  author =	{Lakin, Matthew R. and Kumar, Sarika},
  title =	{{Geometric Enumeration of Localized DNA Strand Displacement Reaction Networks}},
  booktitle =	{30th International Conference on DNA Computing and Molecular Programming (DNA 30)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-344-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{314},
  editor =	{Seki, Shinnosuke and Stewart, Jaimie Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.1},
  URN =		{urn:nbn:de:0030-drops-209294},
  doi =		{10.4230/LIPIcs.DNA.30.1},
  annote =	{Keywords: Localized circuits, reaction enumeration, DNA strand displacement, geometry, molecular computing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.96
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

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

Abstract
We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.
Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  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.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.80
Measure-Theoretic Reeb Graphs and Reeb Spaces

Authors: Qingsong Wang, Guanqun Ma, Raghavendra Sridharamurthy, and Bei Wang

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

Abstract
A Reeb graph is a graphical representation of a scalar function on a topological space that encodes the topology of the level sets. A Reeb space is a generalization of the Reeb graph to a multiparameter function. In this paper, we propose novel constructions of Reeb graphs and Reeb spaces that incorporate the use of a measure. Specifically, we introduce measure-theoretic Reeb graphs and Reeb spaces when the domain or the range is modeled as a metric measure space (i.e., a metric space equipped with a measure). Our main goal is to enhance the robustness of the Reeb graph and Reeb space in representing the topological features of a scalar field while accounting for the distribution of the measure. We first introduce a Reeb graph with local smoothing and prove its stability with respect to the interleaving distance. We then prove the stability of a Reeb graph of a metric measure space with respect to the measure, defined using the distance to a measure or the kernel distance to a measure, respectively.
Cite as

Qingsong Wang, Guanqun Ma, Raghavendra Sridharamurthy, and Bei Wang. Measure-Theoretic Reeb Graphs and Reeb Spaces. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2024.80,
  author =	{Wang, Qingsong and Ma, Guanqun and Sridharamurthy, Raghavendra and Wang, Bei},
  title =	{{Measure-Theoretic Reeb Graphs and Reeb Spaces}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{80:1--80:18},
  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.80},
  URN =		{urn:nbn:de:0030-drops-200257},
  doi =		{10.4230/LIPIcs.SoCG.2024.80},
  annote =	{Keywords: Reeb graph, Reeb space, metric measure space, topological data analysis}
}
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.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.SoCG.2023.25
Meta-Diagrams for 2-Parameter Persistence

Authors: Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang

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

Abstract
We first introduce the notion of meta-rank for a 2-parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the meta-diagram of a 2-parameter persistence module to be the Möbius inversion of the meta-rank, resulting in a function that takes values from signed 1-parameter persistence modules. We show that the meta-rank and meta-diagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the meta-rank and meta-diagram of a 2-parameter module M indexed by a bifiltration of n simplices in O(n³) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n⁴) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n⁴) to O(n³). In addition, we define notions of erosion distance between meta-ranks and between meta-diagrams, and show that under these distances, meta-ranks and meta-diagrams are stable with respect to the interleaving distance. Lastly, the meta-diagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the well-understood persistence diagram in the 1-parameter setting.
Cite as

Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang. Meta-Diagrams for 2-Parameter Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{clause_et_al:LIPIcs.SoCG.2023.25,
  author =	{Clause, Nate and Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Bei},
  title =	{{Meta-Diagrams for 2-Parameter Persistence}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{25:1--25:16},
  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.25},
  URN =		{urn:nbn:de:0030-drops-178754},
  doi =		{10.4230/LIPIcs.SoCG.2023.25},
  annote =	{Keywords: Multiparameter persistence modules, persistent homology, M\"{o}bius inversion, barcodes, computational topology, topological data analysis}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.82
Visual Demo of Discrete Stratified Morse Theory (Media Exposition)

Authors: Youjia Zhou, Kevin Knudson, and Bei Wang

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

Abstract
Discrete stratified Morse theory, first introduced by Knudson and Wang, works toward a discrete analogue of Goresky and MacPherson’s stratified Morse theory. It is inspired by the works of Forman on discrete Morse theory by generalizing stratified Morse theory to finite simplicial complexes. The class of discrete stratified Morse functions is much larger than that of discrete Morse functions. Any arbitrary real-valued function defined on a finite simplicial complex can be made into a discrete stratified Morse function with the proper stratification of the underlying complex. An algorithm is given by Knudson and Wang that constructs a discrete stratified Morse function on any finite simplicial complex equipped with an arbitrary real-valued function. Our media contribution is an open-sourced visualization tool that implements such an algorithm for 2-complexes embedded in the plane, and provides an interactive demo for users to explore the algorithmic process and to perform homotopy-preserving simplification of the resulting stratified complex.
Cite as

Youjia Zhou, Kevin Knudson, and Bei Wang. Visual Demo of Discrete Stratified Morse Theory (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 82:1-82:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.SoCG.2020.82,
  author =	{Zhou, Youjia and Knudson, Kevin and Wang, Bei},
  title =	{{Visual Demo of Discrete Stratified Morse Theory}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{82:1--82:4},
  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.82},
  URN =		{urn:nbn:de:0030-drops-122409},
  doi =		{10.4230/LIPIcs.SoCG.2020.82},
  annote =	{Keywords: Discrete Morse theory, stratified Morse theory, discrete stratified Morse theory, topological data analysis, data visualization}
}
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.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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.3
Vietoris-Rips and Cech Complexes of Metric Gluings

Authors: Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study Vietoris-Rips and Cech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Cech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Cech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.
Cite as

Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier. Vietoris-Rips and Cech Complexes of Metric Gluings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.SoCG.2018.3,
  author =	{Adamaszek, Michal and Adams, Henry and Gasparovic, Ellen and Gommel, Maria and Purvine, Emilie and Sazdanovic, Radmila and Wang, Bei and Wang, Yusu and Ziegelmeier, Lori},
  title =	{{Vietoris-Rips and Cech Complexes of Metric Gluings}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.3},
  URN =		{urn:nbn:de:0030-drops-87162},
  doi =		{10.4230/LIPIcs.SoCG.2018.3},
  annote =	{Keywords: Vietoris-Rips and Cech complexes, metric space gluings and wedge sums, metric graphs, persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.14
Sheaf-Theoretic Stratification Learning

Authors: Adam Brown and Bei Wang

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In this paper, we investigate a sheaf-theoretic interpretation of stratification learning. Motivated by the work of Alexandroff (1937) and McCord (1978), we aim to redirect efforts in the computational topology of triangulated compact polyhedra to the much more computable realm of sheaves on partially ordered sets. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (2012), and the cohomology stratification algorithm given in Nanda (2017). We envision that our sheaf-theoretic algorithm could give rise to a larger class of stratification beyond homology-based stratification. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.
Cite as

Adam Brown and Bei Wang. Sheaf-Theoretic Stratification Learning. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:LIPIcs.SoCG.2018.14,
  author =	{Brown, Adam and Wang, Bei},
  title =	{{Sheaf-Theoretic Stratification Learning}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.14},
  URN =		{urn:nbn:de:0030-drops-87270},
  doi =		{10.4230/LIPIcs.SoCG.2018.14},
  annote =	{Keywords: Sheaf theory, stratification learning, topological data analysis, stratification}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.54
Discrete Stratified Morse Theory: A User's Guide

Authors: Kevin Knudson and Bei Wang

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm that constructs a discrete stratified Morse function out of an arbitrary function defined on a finite simplicial complex; this is different from simply constructing a discrete Morse function on such a complex. We borrow Forman's idea of a "user's guide," where we give simple examples to convey the utility of our theory.
Cite as

Kevin Knudson and Bei Wang. Discrete Stratified Morse Theory: A User's Guide. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{knudson_et_al:LIPIcs.SoCG.2018.54,
  author =	{Knudson, Kevin and Wang, Bei},
  title =	{{Discrete Stratified Morse Theory: A User's Guide}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.54},
  URN =		{urn:nbn:de:0030-drops-87671},
  doi =		{10.4230/LIPIcs.SoCG.2018.54},
  annote =	{Keywords: Discrete Morse theory, stratified Morse theory, topological data analysis}
}
Document
DOI: 10.4230/DagRep.7.7.88
Topology, Computation and Data Analysis (Dagstuhl Seminar 17292)

Authors: Hamish Carr, Michael Kerber, and Bei Wang

Published in: Dagstuhl Reports, Volume 7, Issue 7 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17292 "Topology, Computation and Data Analysis". This seminar was the first of its kind in bringing together researchers with mathematical and computational backgrounds in addressing emerging directions within computational topology for data analysis in practice. The seminar connected pure and applied mathematicians, with theoretical and applied computer scientists with an interest in computational topology. It helped to facilitate interactions among data theorist and data practitioners from several communities to address challenges in computational topology, topological data analysis, and topological visualization.
Cite as

Hamish Carr, Michael Kerber, and Bei Wang. Topology, Computation and Data Analysis (Dagstuhl Seminar 17292). In Dagstuhl Reports, Volume 7, Issue 7, pp. 88-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{carr_et_al:DagRep.7.7.88,
  author =	{Carr, Hamish and Kerber, Michael and Wang, Bei},
  title =	{{Topology, Computation and Data Analysis (Dagstuhl Seminar 17292)}},
  pages =	{88--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{7},
  editor =	{Carr, Hamish and Kerber, Michael and Wang, Bei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.7.88},
  URN =		{urn:nbn:de:0030-drops-84258},
  doi =		{10.4230/DagRep.7.7.88},
  annote =	{Keywords: computational topology, topological data analysis, Topological data visualization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.53
Convergence between Categorical Representations of Reeb Space and Mapper

Authors: Elizabeth Munch and Bei Wang

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit. In this paper, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution.
Cite as

Elizabeth Munch and Bei Wang. Convergence between Categorical Representations of Reeb Space and Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{munch_et_al:LIPIcs.SoCG.2016.53,
  author =	{Munch, Elizabeth and Wang, Bei},
  title =	{{Convergence between Categorical Representations of Reeb Space and Mapper}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.53},
  URN =		{urn:nbn:de:0030-drops-59454},
  doi =		{10.4230/LIPIcs.SoCG.2016.53},
  annote =	{Keywords: Topological data analysis, Reeb space, mapper, category theory}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.857
Geometric Inference on Kernel Density Estimates

Authors: Jeff M. Phillips, Bei Wang, and Yan Zheng

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that geometric inference of a point cloud can be calculated by examining its kernel density estimate with a Gaussian kernel. This allows one to consider kernel density estimates, which are robust to spatial noise, subsampling, and approximate computation in comparison to raw point sets. This is achieved by examining the sublevel sets of the kernel distance, which isomorphically map to superlevel sets of the kernel density estimate. We prove new properties about the kernel distance, demonstrating stability results and allowing it to inherit reconstruction results from recent advances in distance-based topological reconstruction. Moreover, we provide an algorithm to estimate its topology using weighted Vietoris-Rips complexes.
Cite as

Jeff M. Phillips, Bei Wang, and Yan Zheng. Geometric Inference on Kernel Density Estimates. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 857-871, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{phillips_et_al:LIPIcs.SOCG.2015.857,
  author =	{Phillips, Jeff M. and Wang, Bei and Zheng, Yan},
  title =	{{Geometric Inference on Kernel Density Estimates}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{857--871},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.857},
  URN =		{urn:nbn:de:0030-drops-51349},
  doi =		{10.4230/LIPIcs.SOCG.2015.857},
  annote =	{Keywords: topological data analysis, kernel density estimate, kernel distance}
}
Document
DOI: 10.4230/LIPIcs.TQC.2013.192
Symmetries of Codeword Stabilized Quantum Codes

Authors: Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang, and Bei Zeng

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.
Cite as

Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang, and Bei Zeng. Symmetries of Codeword Stabilized Quantum Codes. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 192-206, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{beigi_et_al:LIPIcs.TQC.2013.192,
  author =	{Beigi, Salman and Chen, Jianxin and Grassl, Markus and Ji, Zhengfeng and Wang, Qiang and Zeng, Bei},
  title =	{{Symmetries of Codeword Stabilized Quantum Codes}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{192--206},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.192},
  URN =		{urn:nbn:de:0030-drops-43129},
  doi =		{10.4230/LIPIcs.TQC.2013.192},
  annote =	{Keywords: CWS Codes, Union Stabilizer Codes, Permutation Symmetry, Toric Code}
}
  • Refine by Author
  • 11 Wang, Bei
  • 2 Kerber, Michael
  • 2 Knudson, Kevin
  • 2 Natarajan, Vijay
  • 1 Adamaszek, Michal
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Topology
  • 1 Computer systems organization → Molecular computing
  • 1 Human-centered computing → Visualization
  • 1 Information systems → Data analytics
  • Show More...

  • Refine by Keyword
  • 9 topological data analysis
  • 4 computational topology
  • 2 Discrete Morse theory
  • 2 Reeb space
  • 2 persistent homology
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 4 2018
  • 3 2024
  • 2 2023
  • 1 2013
  • 1 2015
  • Show More...

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