21 votes
Accepted

Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

One major application of topology in semantics is the topological approach to computability. The basic idea of the topology of computability comes from the observation that termination and ...
user avatar
19 votes
Accepted

Why is "topological sorting" topological?

The earliest reference I could find for topological sort is from [Lasser61]: A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal ...
user avatar
  • 3,381
16 votes
Accepted

To what extent can the mathematics of Reals be applied to Computable Reals?

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 ...
user avatar
  • 26.6k
12 votes

Applications of topology to computer science

Nobody has yet mentioned directed algebraic topology, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency. There are also several low ...
user avatar
9 votes

Complexity of Unknotting problems

Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/...
user avatar
  • 7,653
9 votes
Accepted

Barcode of a graph

Betti-0 will be one interval for each vertex, with one of the involved intervals vanishing any time an edge connects two components. This will be very similar to a trace of a Union-Find running on the ...
user avatar
9 votes

Would a purely topological computational model be useful in decision problems in topology?

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three ...
user avatar
  • 824
8 votes
Accepted

Would a purely topological computational model be useful in decision problems in topology?

I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau ...
user avatar
6 votes

Reference request: Shortest homotopic curve via vertex releases

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm. I'm not aware of any exposition of your simple algorithm in the literature. This is actually a little ...
user avatar
  • 22.8k
5 votes
Accepted

The complexity of finding a Borsuk-Ulam point

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence". His ...
user avatar
  • 7,052
4 votes
Accepted

Status of certain problems in knot theory

To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known ...
user avatar
  • 824
4 votes

Status of certain problems in knot theory

Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: https://doi.org/10.1017/...
user avatar
4 votes

Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

The 2004 Gödel Prize was shared between the papers: The Topological Structure of Asynchronous Computation. By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923 Wait-Free k-...
user avatar
  • 2,319
4 votes

Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been ...
user avatar
4 votes

The complexity of finding a Borsuk-Ulam point

How is the oracle given and what do we know about $g$? If the oracle is black-box and we only know that $g$ is continuous odd, then already for $n=1$ we might require infinitely many questions... If ...
user avatar
  • 13.5k
3 votes

Barcode of a graph

The graph is already a simplicial complex comprising of 0 and 1 simplices (nodes and edges). The barcode representation is meaningful only when the simplicial complex is constructed step-by-step such ...
user avatar
  • 31
3 votes

Is the 3-sphere recognition problem NP-complete?

This paper shows (though I have not verified it) that 3-sphere recognition* is in coNP assuming GRH: Raphael Zentner. Integer homology 3-spheres admit irreducible representations in $SL(2,\mathbb{C}...
user avatar
3 votes
Accepted

How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees. (Apologies if the below is extra verbose -- you said that you're new to ...
user avatar
  • 1,624
3 votes
Accepted

What are the application of Scott-Topology in theoretical computer science?

Scott-continuity emerged when Dana Scott build the first model of untyped λ-calculus, while trying to prove that no such model can exist (since any such model $D$ needs to be, simplifying a bit, ...
user avatar
3 votes

Complexity of Unknotting problems

The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness. Unknot recognition in quasipolynomial time outline.. Under the talks section there are slides about the ...
user avatar
  • 1,081
2 votes
Accepted

Data structures for embedded simplicial complexes

First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: ...
user avatar
  • 136
1 vote

Topology/Space of Recursive Algebraic Datatypes

It is possible to construct recursive datatypes (algebraic datatypes are a special case) in a suitable category of complete metric spaces, see for instance P. America and J. Rutten's Solving Reflexive ...
user avatar
  • 26.6k
1 vote

Why is "topological sorting" topological?

Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying ...
user avatar
1 vote

Barcode of a graph

What is said above is correct but I'll add an interesting wrinkle that should be better known. If you use the graph distance as your persistence parameter and then calculate the persistence of the ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible