<p>Topology is such a mature discipline with varied subfields including geometric, algebraic, metric, point-set and (the self deprecating) pointless topology. Computer science is also fairly broad and has many mathematical sub-areas, so I would expect much applications of topological ideas in CS. Marshall Stone said "always topologize," and computer scientists with the requisite background often have. Enough blah. A few examples.</p>

<p>These examples are not just of hard CS problems solved by topology. Sometimes a topological notion transfers very well into a CS setting or gives the basis for a sub area of CS.</p>

<ol>
<li><p>The compactness theorem of propositional logic is a consequence of Tychonoff's theorem. Compactness for first order logic is usually proved differently. Compactness is an important tool in classic model theory.</p></li>
<li><p>Stone's representation theorem for Boolean algebras relates models of propositional logic, Boolean algebras and certain topological spaces. Stone-type duality results have been derived for structures used in algebraic logic and programming language semantics.</p></li>
<li><p>Nick Pippenger applied Stone's theorem to the Boolean algebra of regular languages and used topology to prove several facts about regular languages. See Jean-Eric Pin's comment for more recent work on topology in language theory. </p></li>
<li><p>In formal methods, there are the notions of safety and liveness property. Every linear-time property can be expressed as the intersection of a safety and a liveness property. The proof uses elementary topology. </p></li>
<li><p>Martín Escardó has developed algorithms and written programs to search infinite sets. I believe compactness is a key ingredient of that work.</p></li>
<li><p>The work of Polish topologists (such as Kuratowski) gave us closure operators. Closure operators on lattices are a crucial part of the theory of abstract interpretation, which underlies static program analysis.</p></li>
<li><p>Closure operators and other topological ideas are the basis of mathematical morphology. </p></li>
<li><p>The notion of interior operators also from the Polish school is important in axiomatization of modal logics. </p></li>
<li><p>A lot of computer science is based on graph-based structures. Some applications require richer notions of connectedness and flows than that provided by graphs and topology is the natural next step. This is my reading of van Glabbeek's higher-dimensional automata in concurrency theory and Eric Goubault's application of geometric topology to the semantics of concurrent programs.</p></li>
<li><p>Possibly the application that receives the most press is the application of topology (initially algebraic, though more combinatorial presentations also exist) to characterise certain fault-tolerance scenarios in distributed computing. In addition to Herlihy and Shavit mentioned above, Borowsky and Gafni, and Saks and Zaharouglou also gave proosf for the first such breakthrough. The asynchronous computability framework produced more such results.</p></li>
<li><p>Brouwer's fixed point theorem has given rise to several problems that we study. Most recently in the study of algorithmic game theory, the complexity class PPAD and the complexity class FixP of fixed point problems.</p></li>
<li><p>The Borsuk-Ulam theorem has several applications to graphs and metric embeddings. These are covered in Jiří Matoušek's book. </p></li>
</ol>

<p>These are <em>meagre pickings</em> at what is out there. Good luck!</p>

CC BY-SA 3.0
2011-04-12T19:42:54.520Z
What a great list!
Dave Clarke
CC BY-SA 2.5
2011-04-07T22:24:36.950Z
2011-04-07T22:24:36.950Z
Vijay D
<p>Personally, I think the most interesting application of topology was the work done by Herlihy and Shavit. They used algebraic topology to characterize asynchronous distributed computation and gave new proofs of important known results and knocked out a number of long-standing open problems. They won the 2004 Godel prize for that work.</p>

<p>"The Topological Structure of Asynchronous Computation"
by Maurice Herlihy and Nir Shavit,
Journal of the ACM, Vol. 46 (1999), 858-923, </p>

CC BY-SA 2.5
2010-11-12T06:23:18.017Z
"most interesting" ? now them there's fightin' words ! :)
Suresh Venkat
CC BY-SA 2.5
2010-11-11T23:26:40.670Z
2010-11-11T23:26:40.670Z
Mark Reitblatt
<p>Computable Analysis and computability over $2^{\omega}$.</p>

<p>This is related to Dave's answer and domain theory. The basic argument here is that computability is inherently based on <em>local operations</em> and <em>finite observations</em>. You can think of computability as a refined notion of topology. The most clear example is that:</p>

<blockquote>
  <p>All (oracle Turing) computable functions are continuous. On the other hand, every continuous function is oracle Turing computable with a suitable oracle.</p>
</blockquote>

<p>You can find more in Klaus Weihrauch's book "Computable Analysis".
You may also want to take a look at Steven Vickers' nice book called "Topology via Logic".</p>

CC BY-SA 2.5
2010-11-12T08:08:59.470Z
2010-11-12T09:52:06.543Z
2010-11-12T09:52:06.543Z
Kaveh
<p>Bounds on number of connected components, and more generally Betti numbers, of semi-algebraic varieties and hyperplane arrangements (and their complements) have been used for several lower bounds on algebraic computation and decision trees.  For just a few big references, see:</p>

<blockquote>
  <p>Michael Ben-Or, Lower bounds for algebraic computation trees, STOC 1983, pp. 80-86.</p>
  
  <p>Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, J. Comput. System Sci. 55 (1997),
  no. 1, part 1, 36-43 (STOC 1994).</p>
  
  <p>Anders Bjorner and Laszlo Lovasz, Linear decision trees, subspace arrangements and Mobius functions, J. Amer. Math. Soc. 7 (1994), no. 3, 677-706.</p>
</blockquote>

<hr>

<p>In a different but somewhat related vein, Smale used topology in a pretty interesting manner (in particular, cohomology of the braid group) to lower bound the complexity of root-finding in the Blum-Shub-Smale model:</p>

<blockquote>
  <p>Smale, S. On the topology of algorithms, I.  J. Complexity, 3(2):81-89, 1987.</p>
</blockquote>

CC BY-SA 2.5
2010-11-11T23:42:40.927Z
Those references seem relatively old. Has there been a continuing line of research, or were these fairly one-off results?
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T23:54:18.293Z
Well, I wouldn't call them one-off, since there were a bunch of results using these techniques. I think the more modern results (say from the last decade) either use completely different techniques, or they use more of the semi-algebraic geometry aspect than the topological aspect.
Joshua Grochow
CC BY-SA 2.5
2010-11-12T00:16:21.607Z
(I don't know about Mark's question w.r.t. the Smale result.)
Joshua Grochow
CC BY-SA 4.0
2024-11-29T19:17:37.397Z
Adding more to answer Mark's question: [Mulmuley '99](https://doi.org/10.1137/S0097539794282930) is an extension of these results that is the closest we've come to separating P from NC, but it is not purely topological, it uses additional argument from algebraic geometry.
Joshua Grochow
CC BY-SA 2.5
2010-11-11T23:32:36.897Z
2010-11-12T00:01:32.537Z
2010-11-12T00:01:32.537Z
Joshua Grochow
<p><a href="http://en.wikipedia.org/wiki/Domain_theory">Domain Theory</a> is highly topological in nature, and rather being a one-off application of topology, it is more or less its own subfield of topology. Its application in <a href="http://en.wikipedia.org/wiki/Denotational_semantics">Denotational Semantics</a> of programming languages, especially functional ones, is certainly one of the most important applications of topology in computer science. 
Values (including functions) are given semantics in terms of DCPOs (directed-complete partial orders) or some such structure. Recursive domain equations such as $D\cong [D\to D]$ can be solved in this setting, giving semantics to beasts such as the untyped $\lambda$-calculus. The semantics are fundamentally based on the notion of approximation, given by the ordering, and the least fixed point solution of equations, and solutions are generally guaranteed to exist.</p>

<p>Stemming from denotational semantics are connections with abstract interpretation, and program analysis and verification. </p>

<p>Current research includes providing denotational semantics for concurrency and for quantum languages.</p>

<p>Abramsky and Jung give a nice survey of the core ideas: <a href="http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf">Domain Theory</a>.</p>

CC BY-SA 2.5
2010-11-12T00:43:37.440Z
2010-11-12T17:55:05.053Z
2010-11-12T17:55:05.053Z
Dave Clarke
<p>Don't forget the Kneser conjecture and the Kahn/Saks/Sturtevant proof for the Aandera-Rosenberg-Karp conjecture. </p>

CC BY-SA 2.5
2010-11-12T01:29:26.717Z
2010-11-12T01:29:26.717Z
Suresh Venkat
<p>Theories to understand concurrency and modeling concurrent computations are best understood topologically. Apart from the famous work by Herlihy and Shavit on the topological structure of async computability mentioned in an earlier answer- Eric goubault has done work on <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.1184">Modeling concurrency with geometry</a> and Pratt's work on applications of <a href="http://chu.stanford.edu/guide.html">Chu spaces</a> for concurrency at the Stanford Concurrency group is also interesting although i am not familiar with their work.</p>

CC BY-SA 2.5
2010-11-12T09:36:45.550Z
2010-11-12T09:36:45.550Z
kryptos
<p>Haven't seen mentioned work of <a href="http://www.math.uiuc.edu/~ghrist/index_files/research.htm" rel="nofollow">Robert Ghrist</a>, formerly at Illinois but now at U Penn, applying topology to stuff like sensor networks and robotics. Here is a nice <a href="http://www.johndcook.com/blog/2010/09/13/applied-topology-and-dante-an-interview-with-robert-ghrist/" rel="nofollow">interview.</a></p>

<p>Also very related to work of <a href="http://comptop.stanford.edu/" rel="nofollow">Gunnar Carlsson</a> et al on applying <a href="http://www.ams.org/images/carlsson-notes.pdf" rel="nofollow">topology to data analysis</a>.</p>

<p>Not the STOC/FOCS TCS perhaps, but definitely computer science.</p>

CC BY-SA 3.0
2010-11-13T13:43:09.487Z
2015-11-15T09:31:56.220Z
2015-11-15T09:31:56.220Z
Mugizi Rwebangira
<p>All the work started by Kitaev on the topological approach to a fault tolerant quantum computer. See <a href="http://arxiv.org/abs/quant-ph/9707021">Kitaev's original paper</a> or, for example, John Preskill's <a href="http://www.theory.caltech.edu/~preskill/ph219/topological.pdf">lecture notes</a>. </p>

CC BY-SA 2.5
2010-11-13T22:31:06.383Z
2010-11-13T22:37:10.110Z
2010-11-13T22:37:10.110Z
Alessandro Cosentino
<p>Nobody has yet mentioned <a href="http://en.wikipedia.org/wiki/Directed_algebraic_topology">directed algebraic topology</a>, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency.</p>

<p>There are also several low dimensional topological approaches to topics in the theory of computation, all fairly new:</p>

<ul>
<li>Various approaches to fault-tolerant anyonic quantum computation based on the theory of braids. See e.g. <a href="http://www.site.uottawa.ca/~phil/Ottawa.Traces.07.talks/Kauffman.UnitaryBraids.pdf">HERE</a> and <a href="http://arxiv.org/abs/0707.1889">HERE</a>. Also to networks of adiabatic quantum computations <a href="http://arxiv.org/abs/1404.2862">HERE</a>.</li>
<li>Diagrammatic topology-based formalisms for lambda calculus (e.g. <a href="http://homepages.math.uic.edu/~kauffman/KnotLogic.pdf">HERE</a>, pages 46-48, and <a href="http://arxiv.org/pdf/1312.4333v1.pdf">HERE</a>) and for Milner's pi calculus (<a href="http://arxiv.org/abs/1009.2107">HERE</a>). </li>
<li>Using concatenation of coloured tangles to model recursion and Markov chains. See e.g. <a href="http://homepages.math.uic.edu/~kauffman/KnotAutomata.pdf">HERE</a> and <a href="http://arxiv.org/abs/1404.2862">HERE</a>. In fact it's proven (unpublished) that any Turing machine computation and any recurrent first-order neural network can be modeled in this way.</li>
<li>There is a higher category theoretical formalism for quantum computation in which topological diagrams represent computations, and topologically-equivalent diagrams represent different procedures with identical computational content. See <a href="http://arxiv.org/pdf/1207.4563v1.pdf">HERE</a>.</li>
</ul>

CC BY-SA 3.0
2014-05-27T02:45:27.730Z
2014-05-27T02:56:41.643Z
2014-05-27T02:56:41.643Z
Daniel Moskovich
<p>Some applications to metric embeddings. </p>

<p>Check this book by Matousek : <a href="http://kam.mff.cuni.cz/~matousek/akt.html">http://kam.mff.cuni.cz/~matousek/akt.html</a></p>

<p>Also check out these papers :</p>

<ul>
<li>Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, J. Matousek (1990) ( He uses the van Kampen theorem to prove a lower bound)</li>
<li>Inapproximability for Metric Embeddings into R^d, J. Matousek and A. Sidiropoulos</li>
</ul>

CC BY-SA 2.5
2010-11-20T17:21:45.477Z
2010-11-20T17:21:45.477Z
Zouzias
<p>read this book: </p>

<p>See its <a href="http://web.archive.org/web/20141009165821/http://www.cs.dartmouth.edu/~afra/book.html" rel="nofollow">archived webpage</a></p>

CC BY-SA 2.5
2010-11-12T23:19:34.707Z
I don't know if computational topology is really what he's looking for. Are there applications in there outside of computational topology?
Mark Reitblatt
CC BY-SA 2.5
2010-11-12T23:28:22.107Z
Ummm.  Yes.  Afra's book explicitly discusses surface reconstruction and topological noise removal (which have applications in computer graphics), but there are also applications of computational topology in high-dimensional data analysis, manifold learning, computer vision, image processing, dimensionality reduction, information retrieval, motion planning, etc. etc. etc.
Jeffε
CC BY-SA 3.0
2010-11-12T02:02:02.313Z
2015-11-15T05:21:30.987Z
2015-11-15T05:21:30.987Z
rhl
<p>Two other papers that might be relevant for your survey...</p>

<p>M. Gehrke, S. Grigorieff, J.-E. Pin,   A topological approach to recognition, ICALP 2010, Part II, Lecture Notes in Computer Science 6199, Springer Verlag, (2010), 151-162.</p>

<p>M. Gehrke, S. Grigorieff, J.-E. Pin,   Duality and equational theory of regular languages, Best paper award of ICALP 2008, Track B, ICALP 2008, Part II, Lecture Notes in Computer Science 5126, Springer Verlag, (2008), 246-257. </p>

CC BY-SA 2.5
2011-04-07T13:30:55.557Z
Welcome! I very much enjoyed your survey article "Profinite Methods in Automata Theory".
Neel Krishnaswami
CC BY-SA 2.5
2011-04-07T13:20:58.173Z
2011-04-07T13:20:58.173Z
Jean-Eric Pin
<p>Check this book, <a href="http://www.elsevier.com/wps/find/bookdescription.cws_home/703042/description">Computational Complexity: A Quantitative Perspective,</a>
<a href="http://www.elsevier.com/wps/find/bookdescription.cws_home/703042/description"></a> it studies the size of some complexity classes using resource-bounded topological tools.</p>

<p>It gives interesting topological view on the $P$ vs $NP$ problem. Basically, If $P \ne NP$ then $NP-P$ is topologically not small. The class $NP$-complete is topologically small. According to the author, topological not smallness of $NP-P$ means that it is of the second Baire category.</p>

CC BY-SA 2.5
2010-11-12T20:09:11.217Z
In fact, a lot of work has been done on p-measure and p-category (which is what turkistany is referring to). Jack Lutz introduced this idea, and you can find a ton of papers by looking him up, following links to coauthors and forward references.
Joshua Grochow
CC BY-SA 2.5
2010-11-12T17:42:54.563Z
2010-11-12T18:03:24.150Z
2010-11-12T18:03:24.150Z
Mohammad Al-Turkistany
<p>I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments.  It would be
extremely helpful if anyone could give input regarding any of the
questions below.</p>

<ol>
<li><p>Are there any papers or notes that describe the chronology of the
use of topology in Computer Science?  </p></li>
<li><p>What are the most important application of results in Topology to
Computer Science? </p></li>
<li><p>What are the most interesting areas of current work that use
topology to gain insight into computation? </p></li>
</ol>

<p>Thanks!</p>

CC BY-SA 2.5
2010-11-11T23:34:33.827Z
Several answers to this other question are relevant here: http://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs
Joshua Grochow
CC BY-SA 2.5
2010-11-12T01:28:43.987Z
what about work on algorithms for computing topological objects, or using topological constructs to model data ? does that count ?
Suresh Venkat
CC BY-SA 2.5
2010-11-12T23:30:19.983Z
This is going to be a *LONG* survey.
Jeffε
CC BY-SA 3.0
2015-05-19T15:29:07.887Z
Have you succeeded? A link to your survey wold be appreciated!
Tarc
CC BY-SA 3.0
2015-12-30T04:42:46.207Z
This is a post on a cute application of topology to programming: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/
Holden Lee
<reference-request><ho.history-overview><topology><survey>
Applications of topology to computer science
Ben 
# Applications of topology to computer science

(Asked by: username_0 on 2010-11-11)

I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It would be
extremely helpful if anyone could give input regarding any of the
questions below.

1. Are there any papers or notes that describe the chronology of the
   use of topology in Computer Science?
2. What are the most important application of results in Topology to
   Computer Science?
3. What are the most interesting areas of current work that use
   topology to gain insight into computation?

Thanks!

**Tags:** reference-request, ho.history-overview, topology, survey
> **Comments:**
> **username_1**: Several answers to this other question are relevant here: http://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs  
> **username_2**: what about work on algorithms for computing topological objects, or using topological constructs to model data ? does that count ?  
> **username_3**: This is going to be a *LONG* survey.  
> **username_4**: Have you succeeded? A link to your survey wold be appreciated!  
> **username_5**: This is a post on a cute application of topology to programming: http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/  

---

## 14 answers

### Answer by username_6 on 2011-04-07. Score: 36

Topology is such a mature discipline with varied subfields including geometric, algebraic, metric, point-set and (the self deprecating) pointless topology. Computer science is also fairly broad and has many mathematical sub-areas, so I would expect much applications of topological ideas in CS. Marshall Stone said "always topologize," and computer scientists with the requisite background often have. Enough blah. A few examples.

These examples are not just of hard CS problems solved by topology. Sometimes a topological notion transfers very well into a CS setting or gives the basis for a sub area of CS.

1. The compactness theorem of propositional logic is a consequence of Tychonoff's theorem. Compactness for first order logic is usually proved differently. Compactness is an important tool in classic model theory.
2. Stone's representation theorem for Boolean algebras relates models of propositional logic, Boolean algebras and certain topological spaces. Stone-type duality results have been derived for structures used in algebraic logic and programming language semantics.
3. Nick Pippenger applied Stone's theorem to the Boolean algebra of regular languages and used topology to prove several facts about regular languages. See Jean-Eric Pin's comment for more recent work on topology in language theory.
4. In formal methods, there are the notions of safety and liveness property. Every linear-time property can be expressed as the intersection of a safety and a liveness property. The proof uses elementary topology.
5. Martín Escardó has developed algorithms and written programs to search infinite sets. I believe compactness is a key ingredient of that work.
6. The work of Polish topologists (such as Kuratowski) gave us closure operators. Closure operators on lattices are a crucial part of the theory of abstract interpretation, which underlies static program analysis.
7. Closure operators and other topological ideas are the basis of mathematical morphology.
8. The notion of interior operators also from the Polish school is important in axiomatization of modal logics.
9. A lot of computer science is based on graph-based structures. Some applications require richer notions of connectedness and flows than that provided by graphs and topology is the natural next step. This is my reading of van Glabbeek's higher-dimensional automata in concurrency theory and Eric Goubault's application of geometric topology to the semantics of concurrent programs.
10. Possibly the application that receives the most press is the application of topology (initially algebraic, though more combinatorial presentations also exist) to characterise certain fault-tolerance scenarios in distributed computing. In addition to Herlihy and Shavit mentioned above, Borowsky and Gafni, and Saks and Zaharouglou also gave proosf for the first such breakthrough. The asynchronous computability framework produced more such results.
11. Brouwer's fixed point theorem has given rise to several problems that we study. Most recently in the study of algorithmic game theory, the complexity class PPAD and the complexity class FixP of fixed point problems.
12. The Borsuk-Ulam theorem has several applications to graphs and metric embeddings. These are covered in Jiří Matoušek's book.

These are *meagre pickings* at what is out there. Good luck!

> **Comments:**
> **username_7**: What a great list!  

---

### Answer by username_8 on 2010-11-11. Score: 36

Personally, I think the most interesting application of topology was the work done by Herlihy and Shavit. They used algebraic topology to characterize asynchronous distributed computation and gave new proofs of important known results and knocked out a number of long-standing open problems. They won the 2004 Godel prize for that work.

"The Topological Structure of Asynchronous Computation"
by Maurice Herlihy and Nir Shavit,
Journal of the ACM, Vol. 46 (1999), 858-923,

> **Comments:**
> **username_2**: "most interesting" ? now them there's fightin' words ! :)  

---

### Answer by username_7 on 2010-11-12. Score: 26

[Domain Theory](http://en.wikipedia.org/wiki/Domain_theory) is highly topological in nature, and rather being a one-off application of topology, it is more or less its own subfield of topology. Its application in [Denotational Semantics](http://en.wikipedia.org/wiki/Denotational_semantics) of programming languages, especially functional ones, is certainly one of the most important applications of topology in computer science.
Values (including functions) are given semantics in terms of DCPOs (directed-complete partial orders) or some such structure. Recursive domain equations such as $D\cong [D\to D]$ can be solved in this setting, giving semantics to beasts such as the untyped $\lambda$-calculus. The semantics are fundamentally based on the notion of approximation, given by the ordering, and the least fixed point solution of equations, and solutions are generally guaranteed to exist.

Stemming from denotational semantics are connections with abstract interpretation, and program analysis and verification.

Current research includes providing denotational semantics for concurrency and for quantum languages.

Abramsky and Jung give a nice survey of the core ideas: [Domain Theory](http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf).


---

### Answer by username_9 on 2010-11-12. Score: 19

Computable Analysis and computability over $2^{\omega}$.

This is related to Dave's answer and domain theory. The basic argument here is that computability is inherently based on *local operations* and *finite observations*. You can think of computability as a refined notion of topology. The most clear example is that:

> All (oracle Turing) computable functions are continuous. On the other hand, every continuous function is oracle Turing computable with a suitable oracle.

You can find more in Klaus Weihrauch's book "Computable Analysis".
You may also want to take a look at Steven Vickers' nice book called "Topology via Logic".


---

### Answer by username_1 on 2010-11-11. Score: 19

Bounds on number of connected components, and more generally Betti numbers, of semi-algebraic varieties and hyperplane arrangements (and their complements) have been used for several lower bounds on algebraic computation and decision trees. For just a few big references, see:

> Michael Ben-Or, Lower bounds for algebraic computation trees, STOC 1983, pp. 80-86.
>
> Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, J. Comput. System Sci. 55 (1997),
> no. 1, part 1, 36-43 (STOC 1994).
>
> Anders Bjorner and Laszlo Lovasz, Linear decision trees, subspace arrangements and Mobius functions, J. Amer. Math. Soc. 7 (1994), no. 3, 677-706.

---

In a different but somewhat related vein, Smale used topology in a pretty interesting manner (in particular, cohomology of the braid group) to lower bound the complexity of root-finding in the Blum-Shub-Smale model:

> Smale, S. On the topology of algorithms, I. J. Complexity, 3(2):81-89, 1987.

> **Comments:**
> **username_8**: Those references seem relatively old. Has there been a continuing line of research, or were these fairly one-off results?  
> **username_1**: Well, I wouldn't call them one-off, since there were a bunch of results using these techniques. I think the more modern results (say from the last decade) either use completely different techniques, or they use more of the semi-algebraic geometry aspect than the topological aspect.  
> **username_1**: (I don't know about Mark's question w.r.t. the Smale result.)  
> **username_1**: Adding more to answer Mark's question: [Mulmuley '99](https://doi.org/10.1137/S0097539794282930) is an extension of these results that is the closest we've come to separating P from NC, but it is not purely topological, it uses additional argument from algebraic geometry.  

---

### Answer by username_16 on 2011-04-07. Score: 15

Two other papers that might be relevant for your survey...

M. Gehrke, S. Grigorieff, J.-E. Pin, A topological approach to recognition, ICALP 2010, Part II, Lecture Notes in Computer Science 6199, Springer Verlag, (2010), 151-162.

M. Gehrke, S. Grigorieff, J.-E. Pin, Duality and equational theory of regular languages, Best paper award of ICALP 2008, Track B, ICALP 2008, Part II, Lecture Notes in Computer Science 5126, Springer Verlag, (2008), 246-257.

> **Comments:**
> **username_17**: Welcome! I very much enjoyed your survey article "Profinite Methods in Automata Theory".  

---

### Answer by username_2 on 2010-11-12. Score: 14

Don't forget the Kneser conjecture and the Kahn/Saks/Sturtevant proof for the Aandera-Rosenberg-Karp conjecture.


---

### Answer by username_10 on 2010-11-12. Score: 14

Theories to understand concurrency and modeling concurrent computations are best understood topologically. Apart from the famous work by Herlihy and Shavit on the topological structure of async computability mentioned in an earlier answer- Eric goubault has done work on [Modeling concurrency with geometry](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.1184) and Pratt's work on applications of [Chu spaces](http://chu.stanford.edu/guide.html) for concurrency at the Stanford Concurrency group is also interesting although i am not familiar with their work.


---

### Answer by username_11 on 2010-11-13. Score: 14

Haven't seen mentioned work of [Robert Ghrist](http://www.math.uiuc.edu/~ghrist/index_files/research.htm), formerly at Illinois but now at U Penn, applying topology to stuff like sensor networks and robotics. Here is a nice [interview.](http://www.johndcook.com/blog/2010/09/13/applied-topology-and-dante-an-interview-with-robert-ghrist/)

Also very related to work of [Gunnar Carlsson](http://comptop.stanford.edu/) et al on applying [topology to data analysis](http://www.ams.org/images/carlsson-notes.pdf).

Not the STOC/FOCS TCS perhaps, but definitely computer science.


---

### Answer by username_12 on 2010-11-13. Score: 12

All the work started by Kitaev on the topological approach to a fault tolerant quantum computer. See [Kitaev's original paper](http://arxiv.org/abs/quant-ph/9707021) or, for example, John Preskill's [lecture notes](http://www.theory.caltech.edu/~preskill/ph219/topological.pdf).


---

### Answer by username_13 on 2014-05-27. Score: 12

Nobody has yet mentioned [directed algebraic topology](http://en.wikipedia.org/wiki/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 dimensional topological approaches to topics in the theory of computation, all fairly new:

* Various approaches to fault-tolerant anyonic quantum computation based on the theory of braids. See e.g. [HERE](http://www.site.uottawa.ca/~phil/Ottawa.Traces.07.talks/Kauffman.UnitaryBraids.pdf) and [HERE](http://arxiv.org/abs/0707.1889). Also to networks of adiabatic quantum computations [HERE](http://arxiv.org/abs/1404.2862).
* Diagrammatic topology-based formalisms for lambda calculus (e.g. [HERE](http://homepages.math.uic.edu/~kauffman/KnotLogic.pdf), pages 46-48, and [HERE](http://arxiv.org/pdf/1312.4333v1.pdf)) and for Milner's pi calculus ([HERE](http://arxiv.org/abs/1009.2107)).
* Using concatenation of coloured tangles to model recursion and Markov chains. See e.g. [HERE](http://homepages.math.uic.edu/~kauffman/KnotAutomata.pdf) and [HERE](http://arxiv.org/abs/1404.2862). In fact it's proven (unpublished) that any Turing machine computation and any recurrent first-order neural network can be modeled in this way.
* There is a higher category theoretical formalism for quantum computation in which topological diagrams represent computations, and topologically-equivalent diagrams represent different procedures with identical computational content. See [HERE](http://arxiv.org/pdf/1207.4563v1.pdf).


---

### Answer by username_14 on 2010-11-20. Score: 11

Some applications to metric embeddings.

Check this book by Matousek : <http://kam.mff.cuni.cz/~matousek/akt.html>

Also check out these papers :

* Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, J. Matousek (1990) ( He uses the van Kampen theorem to prove a lower bound)
* Inapproximability for Metric Embeddings into R^d, J. Matousek and A. Sidiropoulos


---

### Answer by username_15 on 2010-11-12. Score: 11

read this book:

See its [archived webpage](http://web.archive.org/web/20141009165821/http://www.cs.dartmouth.edu/~afra/book.html)

> **Comments:**
> **username_8**: I don't know if computational topology is really what he's looking for. Are there applications in there outside of computational topology?  
> **username_3**: Ummm.  Yes.  Afra's book explicitly discusses surface reconstruction and topological noise removal (which have applications in computer graphics), but there are also applications of computational topology in high-dimensional data analysis, manifold learning, computer vision, image processing, dimensionality reduction, information retrieval, motion planning, etc. etc. etc.  

---

### Answer by username_18 on 2010-11-12. Score: 8

Check this book, [Computational Complexity: A Quantitative Perspective,](http://www.elsevier.com/wps/find/bookdescription.cws_home/703042/description)
 it studies the size of some complexity classes using resource-bounded topological tools.

It gives interesting topological view on the $P$ vs $NP$ problem. Basically, If $P \ne NP$ then $NP-P$ is topologically not small. The class $NP$-complete is topologically small. According to the author, topological not smallness of $NP-P$ means that it is of the second Baire category.

> **Comments:**
> **username_1**: In fact, a lot of work has been done on p-measure and p-category (which is what turkistany is referring to). Jack Lutz introduced this idea, and you can find a ton of papers by looking him up, following links to coauthors and forward references.  

---

