Applications of topology to computer science

Question

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!

Answer 1

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,

Answer 2

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!

Answer 3

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 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.

Answer 4

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.

Answer 5

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 6

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.

Answer 7

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

Answer 8

Haven't seen mentioned work of Robert Ghrist, formerly at Illinois but now at U Penn, applying topology to stuff like sensor networks and robotics. Here is a nice interview.

Also very related to work of Gunnar Carlsson et al on applying topology to data analysis.

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

Answer 9

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 and Pratt's work on applications of Chu spaces for concurrency at the Stanford Concurrency group is also interesting although i am not familiar with their work.

Answer 10

All the work started by Kitaev on the topological approach to a fault tolerant quantum computer. See Kitaev's original paper or, for example, John Preskill's lecture notes.

Answer 11

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 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 and HERE. Also to networks of adiabatic quantum computations HERE.
• Diagrammatic topology-based formalisms for lambda calculus (e.g. HERE, pages 46-48, and HERE) and for Milner's pi calculus (HERE).
• Using concatenation of coloured tangles to model recursion and Markov chains. See e.g. HERE and HERE. 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.

Answer 12

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 13

read this book:

See its archived webpage

Answer 14

Check this book, Computational Complexity: A Quantitative Perspective, 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.