Dr Jonathan Spreer

The University of Sydney
jonathan.spreer@sydney.edu.au
Gadget construction


My research interests are motivated by the study of manifolds (i.e., surfaces and their higher-dimensional analogues). For this, I use a blend of techniques from mathematical fields such as low-dimensional topology and combinatorics, tools from computer science, such as parameterised complexity theory, as well as practical skills from algorithm design and the development of mathematical software.

Current research projects


2019 - 2021

Hyam Rubinstein, Jonathan Spreer, Stephan Tillmann, Trisections, triangulations and the complexity of manifolds, Australian Research Council (ARC) Discovery Project 2019, DP190102259.

pic

Abstract:

Topology is the mathematical study of the shape of spaces such as surfaces and their higher dimensional analogues. Geometry endows these spaces, also called manifolds, with additional properties such as distance, angle and curvature. Manifolds can be studied by decomposing them into simple pieces such as triangles. These triangulations are a very effective tool. Typically the fewer pieces they have, the better they describe their underlying manifold. We develop a new approach based on such small triangulations that aims at practical algorithms for manifolds in dimensions 3 and 4. Concrete aims include connectivity results for triangulations, and algorithms to recognise fundamental topological structures such as trisections and bundles.

Past research projects


2015 - 2018

Benjamin A. Burton, Jonathan Spreer, Tractable topological computing: Escaping the hardness trap, Australian Research Council (ARC) Discovery Project 2015, DP150104108.

FPT

Abstract:

Computational topology is a young and energetic field that uses computers to solve complex geometric problems driven by pure mathematics, and with diverse applications in biology, signal processing and data mining. A major barrier is that many of these problems are thought to be fundamentally and intractably hard. This project will defy such barriers for typical real-world inputs by fusing geometric techniques with technologies from the field of parameterised complexity, creating powerful, practical solutions for these problems. It will shed much-needed light on the vast and puzzling gap between theory and practice, and give researchers fast new software tools for large-scale experimentation and cutting-edge computer proofs.

2014 - 2016

Benjamin A. Burton, Basudeb Datta, Jonathan Spreer, Nitin Singh, Building triangulations for fast topological computing, DIICCSRTE, Australia-India Strategic Research Fund (AISRF), Round 7, AISRF06660.

Elliptic curve

Abstract:

Computational topology is a young and fast-growing area of ICT, with roots in geometry and applications in biology, physics, computer vision and cosmology, in which real computations are often prohibitively expensive. We will overcome this by building "tight triangulations", highly efficient forms of input with which we can solve substantial problems cheaply using new and innovative heuristics. Outcomes will include practical software, with significant benefits spanning both ICT and mathematics.

Publications


My articles on arXiv.org
  Preprints
pic (with Giulia Codenotti and Francisco Santos) Separation-type combinatorial invariants for triangulations of manifolds, 2018. 33 pages, 5 figures arXiv:1808.04220 [math.CO]. [ bib | arXiv ]
pic (with William Jaco, Hyam Rubinstein and Stephan Tillmann) On minimal ideal triangulations of cusped hyperbolic 3-manifolds, 2018. 30 pages, 16 figures, arXiv:1808.02836 [math.GT]. [ bib | arXiv ]
pic (with Jorge Olarte and Francisco Santos) Short proof of two cases of Chvátal's conjecture, 2018. 3 pages, arXiv:1804.03646 [math.CO]. [ bib | arXiv ]
pic (with William Jaco, Hyam Rubinstein and Stephan Tillmann) Z2-Thurston Norm and Complexity of 3-Manifolds, II., 2017. 21 pages, 10 figures, arXiv:1711.10737 [math.GT]. [ bib | arXiv ]
pic (with Jorge Olarte, Francisco Santos and Christian Stump) Pure flag simplicial complexes and the Erdős-Ko-Rado-property, 2017. 23 pages, 2 figures, arXiv:1710.02518 [math.CO]. [ bib | arXiv ]
pic (with Benjamin A. Burton and Basudeb Datta) The Pachner graph of 2-spheres, 2017. 23 pages, 20 figures, 1 table, arXiv:1701.05144 [math.CO]. [ bib | arXiv ]
pic (with João Paixão) Random collapsibility and 3-sphere recognition, 2015. 18 pages, 6 figures, arXiv:1509.07607 [math.GT]. [ bib | arXiv ]
  Published
pic (with Benjamin A. Burton and Clément Maria) Algorithms and complexity for Turaev-Viro invariants. Journal of Applied and Computational Topology, DOI 10.1007/s41468-018-0016-2, 1-21, 2018. [ bib | arXiv | doi ]
pic (with Stephan Tillmann) Unravelling the Dodecahedral Spaces. 2016 MATRIX Annals In MATRIX Book Ser. (Springer, Cham), vol. 1, pg. 323--347, 2018. [ bib | arXiv | doi ]
pic (with Kristóf Huszár and Uli Wagner) On the treewidth of triangulated 3-manifolds. 34nd International Symposium on Computational Geometry (SoCG 2018). In Leibniz International Proceedings in Informatics (LIPICS), vol. 99, pg. 46:1-46:15, 2018. [ bib | arXiv | doi ]
pic (with Stephan Tillmann) Determining the trisection genus of orientable and non-orientable PL 4-manifolds through triangulations. 34nd International Symposium on Computational Geometry (SoCG 2018). In Leibniz International Proceedings in Informatics (LIPICS), vol. 99, pg. 71:1-71:13, 2018. [ bib | arXiv | doi ]
pic (with Clément Maria) A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2721-2732, 2017. [ bib | arXiv ]
pic (with Bhaskar Bagchi and Basudeb Datta) A characterization of tightly triangulated 3-manifolds. European J. Combin., 61:133-137, 2017. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton) Combinatorial Seifert fibred spaces with transitive cyclic automorphism group. Israel Journal of Mathematics, 214(2):741-784, 2016. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton, Basudeb Datta and Nitin Singh) A construction principle for tight and minimal triangulations of manifolds. Experimental Mathematics, 27:22-36, 2018. [ bib | arXiv | doi ]
pic (with Clément Maria) Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants. 24th Annual European Symposium on Algorithms (ESA 2016). In Leibniz International Proceedings in Informatics (LIPIcs), vol. 57, pg. 64:1-64:16, 2016. [ bib | arXiv | doi ]
pic (with William Jaco, Jesse Johnson and Stephan Tillmann) Bounds for the genus of a normal surface. Geometry and Topology, 20(3):1625-1671, 2016. [ bib |  arXiv | doi ]
pic (with Bhaskar Bagchi, Benjamin A. Burton, Basudeb Datta and Nitin Singh) Efficient algorithms to decide tightness. 32nd International Symposium on Computational Geometry (SoCG 2016). In Leibniz International Proceedings in Informatics (LIPICS), vol. 51, pg. 12:1-12:15, 2016. [ bib | arXiv | doi ]
pic (with Bhaskar Bagchi and Basudeb Datta) Tight triangulations of closed 3-manifolds. European J. Combin., 54:103-120, 2016. [ bib | arXiv | doi ]
pic (with Biplab Basak) Simple crystallizations of 4-manifolds. Advances in Geometry, 16(1):111-130, 2016. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton, Thomas Lewiner and João Paixão) Parameterized complexity of discrete Morse theory. ACM Trans. Math. Softw., 42(1):24 pages, 2016. [ bib | arXiv | doi ]
pic Necessary conditions for the tightness of odd-dimensional combinatorial manifolds. European J. Combin., 51:475-491, 2016. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton, Basudeb Datta and Nitin Singh) Separation index of graphs and stacked 2-spheres. J. Combin. Theory (A), 136:184-197, 2015. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton and Clément Maria) Algorithms and complexity for Turaev-Viro invariants. Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 1, pg. 281-293. [ bib | arXiv | doi ]
pic Combinatorial 3-manifolds with transitive cyclic automorphism group. Discrete and Computational Geometry, 51(2):394-426, 2014. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton, Thomas Lewiner and João Paixão) Parameterized complexity of discrete Morse theory. Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry (SoCG), pg. 127-136, 2013. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton and João Paixão) Computational topology and normal surfaces: Theoretical and experimental complexity bounds. Proceedings of the Meeting on Algorithm Engineering and Experiments, pg. 78-87, 2013. [ bib | arXiv | doi ]
pic (with Benjamin A. Burton) The complexity of detecting taut angle structures on triangulations. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pg. 168-183, 2013. [ bib | arXiv | doi ]
pic Partitioning the triangles of the cross polytope into surfaces. Beitr. Algebra Geom. / Contributions to Algebra and Geometry, 53(2):473-486, 2012. [ bib | http | arXiv | doi ]
pic Normal surfaces as combinatorial slicings. Discrete Math., 311(14):1295-1309, 2011. [ bib | arXiv | doi ]
pic (with Wolfgang Kühnel) Combinatorial properties of the K3 surface: Simplicial blowups and slicings. Exp. Math., 20(2):201-216, 2011. [ bib | http | arXiv | doi ]
  Informal review only
pic (with Clément Maria) Classification of Normal Curves on a Tetrahedron. 32nd Symposium on Computational Geometry, Young Researchers Forum, Collections of abstracts, 2016. [ bib | arXiv ]
pic Random Collapsibility and 3-sphere recognition. Computational Geometric and Algebraic Topology. In Oberwolfach reports, vol. 12(4), 2662-2665, 2015. [ bib | doi ]
pic (with Benjamin A. Burton) Computationally proving triangulated 4-manifolds to be diffeomorphic. 29th ACM Symposium on Computational Geometry, Young Researchers Forum, Collections of abstracts, 2013, pages 15-16. [ bib | arXiv ]
pic (with Felix Effenberger) Simplicial blowups and discrete normal surfaces in the GAP package simpcomp. ACM Communications in Computer Algebra, 45(3):173-176, 2011. [ bib | arXiv | doi ]
pic (with Felix Effenberger) simpcomp - a GAP toolbox for simplicial complexes. ACM Communications in Computer Algebra, 44(4):186-189, 2010. [ bib | doi ]
  Mathematical software
pic (with Felix Effenberger) simpcomp - A GAP package, Version 2.1.5, 2009-2016. [ bib | http ]
  Editorship
pic Jonathan Spreer, Uli Wagner (Organisers), Benjamin A. Burton, Satoshi Murai, Eric Sedgwick, Henry Segerman. Collection of abstracts of the Workshop on Triangulations in Geometry and Topology at CG Week 2014 in Kyoto. 4 x 6 page extended abstracts. The workshop was held as part of CG-Week 2014 at Kyoto University. June 10th, 2014 [ bib | arXiv | http ]
  Theses
pic Blowups, slicings and permutation groups in combinatorial topology. Logos Verlag Berlin, 2011. Dissertation. [ bib | http ]
pic Über die Topologie von kombinatorischen 4-Mannigfaltigkeiten, insbesondere der K3-Fläche, 2008. Diplomarbeit. [ bib ]

Selected talks


Dec 2015 Talk at the 39th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, Brisbane, Australia.
Title: Separation index of graphs and stacked 2-sphere
slides ]
Oct 2015 Talks at Institute for Science and Technology, Klosterneuburg, Austria; Technische Universität Berlin, Germany; Indian Institute of Science, Bangalore, India; and Indian Statistical Institute, Calcutta, India.
Title: Algorithms and complexity for Turaev-Viro invariants
slides ]
Oct 2015 Presentation at Mathematical Research Institute Oberwolfach, see extended abstract above.
Title: Random collapsibility and 3-sphere recognition
slides (from the 2015 AustMS meeting in Adelaide) ]
Jun 2015 Talk at Freie Universität Berlin, Germany.
Title: Parameterised complexity theory for topological problems
slides (from the 2013 AustMS meeting in Sydney) ]
Feb 2015 Talk at University of Ulm, Germany.
Title: Geometrie und Topologie im Computeralgebrasystem GAP
slides ]
May 2014 Talk at the National Institute of Informatics Shonan Meeting on Knot theory, Algorithms, complexity and computation, Tokyo, Japan.
Title: Tightness for triangulations
slides (from the 2014 AustMS meeting in Melbourne) ]
Apr 2014 Talk at the Computational and Algorithmic Topology workshop (CATS), Sydney, Australia.
Title: Bounds for the genus of a normal surface
slides ]

Dr Jonathan Spreer   |   The University of Sydney   |   School of Mathematics and Statistics   |   Email: jonathan.spreer@sydney.edu.au