9
$\begingroup$

I am an homotopy theorist, interested in computer science.

I would like to ask what are some interesting applications of homotopical algebra (model categories, infinity categories, simplicial categories, etc) in theoretical computer science?

$\endgroup$
  • $\begingroup$ Related: here and here. $\endgroup$ – hengxin Jul 22 '16 at 1:45
3
$\begingroup$

Two big applications of homotopy theory in theoretical computer science are

  1. Homotopy Type Theory revealed a completely unexpected connection between the theory of the typed lambda calculus and homotopy theory. As a quick intuition, think of it as either a (vast) generalization of the connection between intuitionistic logic and topological spaces, or a language for doing "synthetic homotopy theory".

  2. The directed version of algebraic topology and homotopy theory (ie, where paths are not reversible) has been developed precisely with applications to computer science in mind. The intuition is that the possible evaluations of a concurrent program correspond to a space, program executions correspond to paths in that space, and synchronization primitives correspond to obstructions. By considering the geometric properties of these spaces/programs, it becomes possible to develop tools for reasoning about their behaviour.

$\endgroup$
2
$\begingroup$

My answer to a related post: Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?:

The 2004 Gödel Prize was shared by the following two 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-Set Agreement Is Impossible: The Topology of Public Knowledge.
    By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483.

Quotes from the 2004 Gödel Prize:

The two papers offer one of the most important breakthroughs in the theory of distributed computing.

The discovery of the topological nature of distributed computing provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.


Added:

A book on this topic:

Distributed Computing Through Combinatorial Topology, 1st Edition, 2013

$\endgroup$
  • $\begingroup$ While I am a big fan of these results, it's not clear to me if they count as homotopical algebra so much as just homological algebra... $\endgroup$ – Joshua Grochow Jul 22 '16 at 16:14
  • $\begingroup$ @JoshuaGrochow Honestly, I know little about these results. I am interested in distributed computing and know of these results. However, I have little mathematical background to understand them well. Please feel free to modify/delete my answer. Thanks. $\endgroup$ – hengxin Jul 23 '16 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.