13 Search Results for "Burton, Benjamin A."

Document
DOI: 10.4230/LIPIcs.AFT.2024.24
Investigating Wrench Attacks: Physical Attacks Targeting Cryptocurrency Users

Authors: Marilyne Ordekian, Gilberto Atondo-Siu, Alice Hutchings, and Marie Vasek

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
Cryptocurrency wrench attacks are physical attacks targeting cryptocurrency users in the real world to illegally obtain cryptocurrencies. These attacks significantly undermine the efficacy of existing digital security norms when confronted with real-world threats. We present the first comprehensive study on wrench attacks. We propose a theoretical approach to defining wrench attacks per criminal law norms, and an interdisciplinary empirical approach to measure their incidence. Leveraging three data sources, we perform crime script analysis, detecting incidents globally across 10 interviews with victims and experts, 146 news articles, and 37 online forums. Our findings reveal diverse groups of attackers ranging from organized crime groups to friends and family, various modi operandi, and different forms of attacks varying from blackmail to murder. Despite existing since Bitcoin’s early days, these attacks are underreported due to revictimization fears. Additionally, unlike other cryptocurrency crimes, users with advanced security experience were not immune to them. We identify potential vulnerabilities in users' behavior and encourage cryptocurrency holders to lean into digital as well as physical safety measures to protect themselves and their cryptocurrency. We offer actionable recommendations for the security community and regulators, highlighting the double-edged sword of Know Your Customer policies.
Cite as

Marilyne Ordekian, Gilberto Atondo-Siu, Alice Hutchings, and Marie Vasek. Investigating Wrench Attacks: Physical Attacks Targeting Cryptocurrency Users. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 24:1-24:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ordekian_et_al:LIPIcs.AFT.2024.24,
  author =	{Ordekian, Marilyne and Atondo-Siu, Gilberto and Hutchings, Alice and Vasek, Marie},
  title =	{{Investigating Wrench Attacks: Physical Attacks Targeting Cryptocurrency Users}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{24:1--24:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.24},
  URN =		{urn:nbn:de:0030-drops-209609},
  doi =		{10.4230/LIPIcs.AFT.2024.24},
  annote =	{Keywords: cryptocurrency, Bitcoin, crime, wrench attack, physical attack}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.22
Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads

Authors: Xiaofei Carl Zang, Xiang Li, Kyle Metcalfe, Tuval Ben-Yehezkel, Ryan Kelley, and Mingfu Shao

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Modern sequencing technologies allow for the addition of short-sequence tags, known as anchors, to both ends of a captured molecule. Anchors are useful in assembling the full-length sequence of a captured molecule as they can be used to accurately determine the endpoints. One representative of such anchor-enabled technology is LoopSeq Solo, a synthetic long read (SLR) sequencing protocol. LoopSeq Solo also achieves ultra-high sequencing depth and high purity of short reads covering the entire captured molecule. Despite the availability of many assembly methods, constructing full-length sequence from these anchor-enabled, ultra-high coverage sequencing data remains challenging due to the complexity of the underlying assembly graphs and the lack of specific algorithms leveraging anchors. We present Anchorage, a novel assembler that performs anchor-guided assembly for ultra-high-depth sequencing data. Anchorage starts with a kmer-based approach for precise estimation of molecule lengths. It then formulates the assembly problem as finding an optimal path that connects the two nodes determined by anchors in the underlying compact de Bruijn graph. The optimality is defined as maximizing the weight of the smallest node while matching the estimated sequence length. Anchorage uses a modified dynamic programming algorithm to efficiently find the optimal path. Through both simulations and real data, we show that Anchorage outperforms existing assembly methods, particularly in the presence of sequencing artifacts. Anchorage fills the gap in assembling anchor-enabled data. We anticipate its broad use as anchor-enabled sequencing technologies become prevalent. Anchorage is freely available at https://github.com/Shao-Group/anchorage; the scripts and documents that can reproduce all experiments in this manuscript are available at https://github.com/Shao-Group/anchorage-test.
Cite as

Xiaofei Carl Zang, Xiang Li, Kyle Metcalfe, Tuval Ben-Yehezkel, Ryan Kelley, and Mingfu Shao. Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zang_et_al:LIPIcs.WABI.2024.22,
  author =	{Zang, Xiaofei Carl and Li, Xiang and Metcalfe, Kyle and Ben-Yehezkel, Tuval and Kelley, Ryan and Shao, Mingfu},
  title =	{{Anchorage Accurately Assembles Anchor-Flanked Synthetic Long Reads}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.22},
  URN =		{urn:nbn:de:0030-drops-206660},
  doi =		{10.4230/LIPIcs.WABI.2024.22},
  annote =	{Keywords: Genome assembly, de Bruijn graph, synthetic long reads, anchor-guided assembly, LoopSeq}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2024.5
The Flower Calculus

Authors: Pablo Donato

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract
We introduce the flower calculus, a deep inference proof system for intuitionistic first-order logic inspired by Peirce’s existential graphs. It works as a rewriting system over inductive objects called "flowers", that enjoy both a graphical interpretation as topological diagrams, and a textual presentation as nested sequents akin to coherent formulas. Importantly, the calculus dispenses completely with the traditional notion of symbolic connective, operating solely on nested flowers containing atomic predicates. We prove both the soundness of the full calculus and the completeness of an analytic fragment with respect to Kripke semantics. This provides to our knowledge the first analyticity result for a proof system based on existential graphs, adapting semantic cut-elimination techniques to a deep inference setting. Furthermore, the kernel of rules targetted by completeness is fully invertible, a desirable property for both automated and interactive proof search.
Cite as

Pablo Donato. The Flower Calculus. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{donato:LIPIcs.FSCD.2024.5,
  author =	{Donato, Pablo},
  title =	{{The Flower Calculus}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.5},
  URN =		{urn:nbn:de:0030-drops-203343},
  doi =		{10.4230/LIPIcs.FSCD.2024.5},
  annote =	{Keywords: deep inference, graphical calculi, existential graphs, intuitionistic logic, Kripke semantics, cut-elimination}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2024.30
homotopy.io: A Proof Assistant for Finitely-Presented Globular n-Categories

Authors: Nathan Corbyn, Lukas Heidemann, Nick Hu, Chiara Sarti, Calin Tataru, and Jamie Vicary

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract
We present the proof assistant homotopy.io for working with finitely-presented semistrict higher categories. The tool runs in the browser with a point-and-click interface, allowing direct manipulation of proof objects via a graphical representation. We describe the user interface and explain how the tool can be used in practice. We also describe the essential subsystems of the tool, including collapse, contraction, expansion, typechecking, and layout, as well as key implementation details including data structure encoding, memoisation, and rendering. These technical innovations have been essential for achieving good performance in a resource-constrained setting.
Cite as

Nathan Corbyn, Lukas Heidemann, Nick Hu, Chiara Sarti, Calin Tataru, and Jamie Vicary. homotopy.io: A Proof Assistant for Finitely-Presented Globular n-Categories. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 30:1-30:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{corbyn_et_al:LIPIcs.FSCD.2024.30,
  author =	{Corbyn, Nathan and Heidemann, Lukas and Hu, Nick and Sarti, Chiara and Tataru, Calin and Vicary, Jamie},
  title =	{{homotopy.io: A Proof Assistant for Finitely-Presented Globular n-Categories}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{30:1--30:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.30},
  URN =		{urn:nbn:de:0030-drops-203594},
  doi =		{10.4230/LIPIcs.FSCD.2024.30},
  annote =	{Keywords: Higher category theory, proof assistant, string diagrams}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.30
Effective Computation of the Heegaard Genus of 3-Manifolds

Authors: Benjamin A. Burton and Finn Thompson

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

Abstract
The Heegaard genus is a fundamental invariant of 3-manifolds. However, computing the Heegaard genus of a triangulated 3-manifold is NP-hard, and while algorithms exist, little work has been done in making such an algorithm efficient and practical for implementation. Current algorithms use almost normal surfaces, which are an extension of the algorithm-friendly normal surface theory but which add considerable complexity for both running time and implementation. Here we take a different approach: instead of working with almost normal surfaces, we give a general method of modifying the input triangulation that allows us to avoid almost normal surfaces entirely. The cost is just four new tetrahedra, and the benefit is that important surfaces that were once almost normal can be moved to the simpler setting of normal surfaces in the new triangulation. We apply this technique to the computation of Heegaard genus, where we develop algorithms and heuristics that prove successful in practice when applied to a data set of 3,000 closed hyperbolic 3-manifolds; we precisely determine the genus for at least 2,705 of these.
Cite as

Benjamin A. Burton and Finn Thompson. Effective Computation of the Heegaard Genus of 3-Manifolds. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.SoCG.2024.30,
  author =	{Burton, Benjamin A. and Thompson, Finn},
  title =	{{Effective Computation of the Heegaard Genus of 3-Manifolds}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{30:1--30: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.30},
  URN =		{urn:nbn:de:0030-drops-199750},
  doi =		{10.4230/LIPIcs.SoCG.2024.30},
  annote =	{Keywords: 3-manifolds, triangulations, normal surfaces, computational topology, Heegaard genus}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.21
Finding Large Counterexamples by Selectively Exploring the Pachner Graph

Authors: Benjamin A. Burton and Alexander He

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

Abstract
We often rely on censuses of triangulations to guide our intuition in 3-manifold topology. However, this can lead to misplaced faith in conjectures if the smallest counterexamples are too large to appear in our census. Since the number of triangulations increases super-exponentially with size, there is no way to expand a census beyond relatively small triangulations - the current census only goes up to 10 tetrahedra. Here, we show that it is feasible to search for large and hard-to-find counterexamples by using heuristics to selectively (rather than exhaustively) enumerate triangulations. We use this idea to find counterexamples to three conjectures which ask, for certain 3-manifolds, whether one-vertex triangulations always have a "distinctive" edge that would allow us to recognise the 3-manifold.
Cite as

Benjamin A. Burton and Alexander He. Finding Large Counterexamples by Selectively Exploring the Pachner Graph. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.SoCG.2023.21,
  author =	{Burton, Benjamin A. and He, Alexander},
  title =	{{Finding Large Counterexamples by Selectively Exploring the Pachner Graph}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-178712},
  doi =		{10.4230/LIPIcs.SoCG.2023.21},
  annote =	{Keywords: Computational topology, 3-manifolds, Triangulations, Counterexamples, Heuristics, Implementation, Pachner moves, Bistellar flips}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.25
The Next 350 Million Knots

Authors: Benjamin A. Burton

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

Abstract
The tabulation of all prime knots up to a given number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we extend the tables from 16 to 19 crossings, with a total of 352 152 252 distinct non-trivial prime knots. The tabulation has two major stages: (1) a combinatorial enumeration stage, which involves generating a provably sufficient set of candidate knot diagrams; and (2) a computational topology stage, which involves identifying and removing duplicate knots, and certifying that all knots that remain are topologically distinct. In this paper we describe the many different algorithmic components in this process, which draw on graph theory, hyperbolic geometry, knot polynomials, normal surface theory, and computational algebra. We also discuss the algorithm engineering challenges in solving difficult topological problems systematically and reliably on hundreds of millions of inputs, despite the fact that no reliably fast algorithms for these problems are known.
Cite as

Benjamin A. Burton. The Next 350 Million Knots. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{burton:LIPIcs.SoCG.2020.25,
  author =	{Burton, Benjamin A.},
  title =	{{The Next 350 Million Knots}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-121831},
  doi =		{10.4230/LIPIcs.SoCG.2020.25},
  annote =	{Keywords: Computational topology, knots, 3-manifolds, implementation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.18
The HOMFLY-PT Polynomial is Fixed-Parameter Tractable

Authors: Benjamin A. Burton

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

Abstract
Many polynomial invariants of knots and links, including the Jones and HOMFLY-PT polynomials, are widely used in practice but #P-hard to compute. It was shown by Makowsky in 2001 that computing the Jones polynomial is fixed-parameter tractable in the treewidth of the link diagram, but the parameterised complexity of the more powerful HOMFLY-PT polynomial remained an open problem. Here we show that computing HOMFLY-PT is fixed-parameter tractable in the treewidth, and we give the first sub-exponential time algorithm to compute it for arbitrary links.
Cite as

Benjamin A. Burton. The HOMFLY-PT Polynomial is Fixed-Parameter Tractable. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{burton:LIPIcs.SoCG.2018.18,
  author =	{Burton, Benjamin A.},
  title =	{{The HOMFLY-PT Polynomial is Fixed-Parameter Tractable}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{18:1--18: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.18},
  URN =		{urn:nbn:de:0030-drops-87311},
  doi =		{10.4230/LIPIcs.SoCG.2018.18},
  annote =	{Keywords: Knot theory, knot invariants, parameterised complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.23
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors: Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
Cite as

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.ESA.2017.23,
  author =	{Burton, Benjamin and Chambers, Erin and van Kreveld, Marc and Meulemans, Wouter and Ophelders, Tim and Speckmann, Bettina},
  title =	{{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.23},
  URN =		{urn:nbn:de:0030-drops-78630},
  doi =		{10.4230/LIPIcs.ESA.2017.23},
  annote =	{Keywords: Fr\'{e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.18
The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex

Authors: Benjamin Burton, Sergio Cabello, Stefan Kratsch, and William Pettersson

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^(o(sqrt(k)))) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).
Cite as

Benjamin Burton, Sergio Cabello, Stefan Kratsch, and William Pettersson. The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.STACS.2017.18,
  author =	{Burton, Benjamin and Cabello, Sergio and Kratsch, Stefan and Pettersson, William},
  title =	{{The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.18},
  URN =		{urn:nbn:de:0030-drops-70156},
  doi =		{10.4230/LIPIcs.STACS.2017.18},
  annote =	{Keywords: computational topology, parameterized complexity, simplicial complex}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.12
Efficient Algorithms to Decide Tightness

Authors: Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer

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

Abstract
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.
Cite as

Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer. Efficient Algorithms to Decide Tightness. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bagchi_et_al:LIPIcs.SoCG.2016.12,
  author =	{Bagchi, Bhaskar and Datta, Basudeb and Burton, Benjamin A. and Singh, Nitin and Spreer, Jonathan},
  title =	{{Efficient Algorithms to Decide Tightness}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{12:1--12:15},
  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.12},
  URN =		{urn:nbn:de:0030-drops-59040},
  doi =		{10.4230/LIPIcs.SoCG.2016.12},
  annote =	{Keywords: discrete geometry and topology, polynomial time algorithms, fixed parameter tractability, tight triangulations, simplicial complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.24
Finding Non-Orientable Surfaces in 3-Manifolds

Authors: Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner

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

Abstract
We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.
Cite as

Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. Finding Non-Orientable Surfaces in 3-Manifolds. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.SoCG.2016.24,
  author =	{Burton, Benjamin A. and de Mesmay, Arnaud and Wagner, Uli},
  title =	{{Finding Non-Orientable Surfaces in 3-Manifolds}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{24:1--24:15},
  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.24},
  URN =		{urn:nbn:de:0030-drops-59168},
  doi =		{10.4230/LIPIcs.SoCG.2016.24},
  annote =	{Keywords: 3-manifold, low-dimensional topology, embedding, non-orientability, normal surfaces}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.270
An Edge-Based Framework for Enumerating 3-Manifold Triangulations

Authors: Benjamin A. Burton and William Pettersson

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

Abstract
A typical census of 3-manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Although censuses are useful resources for mathematicians, constructing them is difficult: the best algorithms to date have not gone beyond n=12. The underlying algorithms essentially (i) enumerate all relevant 4-regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3-manifold triangulations with G as their dual 1-skeleton, of which there could be exponentially many. In practice, a small number of multigraphs often dominate the running times of census algorithms: for example, in a typical census on 10 tetrahedra, almost half of the running time is spent on just 0.3% of the graphs. Here we present a new algorithm for stage (ii), which is the computational bottleneck in this process. The key idea is to build triangulations by recursively constructing neighbourhoods of edges, in contrast to traditional algorithms which recursively glue together pairs of tetrahedron faces. We implement this algorithm, and find experimentally that whilst the overall performance is mixed, the new algorithm runs significantly faster on those "pathological" multigraphs for which existing methods are extremely slow. In this way the old and new algorithms complement one another, and together can yield significant performance improvements over either method alone.
Cite as

Benjamin A. Burton and William Pettersson. An Edge-Based Framework for Enumerating 3-Manifold Triangulations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 270-284, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.SOCG.2015.270,
  author =	{Burton, Benjamin A. and Pettersson, William},
  title =	{{An Edge-Based Framework for Enumerating 3-Manifold Triangulations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{270--284},
  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.270},
  URN =		{urn:nbn:de:0030-drops-51485},
  doi =		{10.4230/LIPIcs.SOCG.2015.270},
  annote =	{Keywords: triangulations, enumeration, graph theory}
}
  • Refine by Author
  • 7 Burton, Benjamin A.
  • 2 Burton, Benjamin
  • 2 Pettersson, William
  • 1 Atondo-Siu, Gilberto
  • 1 Bagchi, Bhaskar
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Topology
  • 1 Applied computing → Digital cash
  • 1 Applied computing → Law
  • 1 Applied computing → Molecular sequence analysis
  • 1 Security and privacy → Social aspects of security and privacy
  • Show More...

  • Refine by Keyword
  • 3 3-manifolds
  • 2 Computational topology
  • 2 computational topology
  • 2 normal surfaces
  • 2 triangulations
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 5 2024
  • 2 2016
  • 2 2017
  • 1 2015
  • 1 2018
  • 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