I have just discovered the paper of M. Herlihy and N. Shavit on the use of algebraic topology methods in TCS and distributed computing in particular.

Now I am wondering if there is any further work being done in this area and if there are any current interesting follow up papers. Does anyone know anything about the state of the art?

Thank you!

  • 4
    $\begingroup$ Check out Eric Goubault's work on algebraic topology and parallelism, e.g. this book $\endgroup$ May 14 at 12:55
  • 1
    $\begingroup$ Bounds on Betty numbers of the set of zeros of polynomials (such as those given by Milnor and Thom) are used to prove bounds on the number of certain structures (such as order types) in discrete and computational geometry. The works of Ben-or, Yao, etc., giving lower bounds for the complexity of algebraic decision trees also comes to mind (a lot of work on algebraic decision/computation trees in general could fit). $\endgroup$
    – Tassle
    May 14 at 14:33
  • 1
    $\begingroup$ When you say "further work in this area" are you asking specifically about applying algebraic topology to distributed computing? Or more generally applications of algebraic topology in TCS? $\endgroup$ May 15 at 2:22
  • 1
    $\begingroup$ Maybe the title of the question is missleading. I was asking for further work specifically applying algebraic topology to distributed computing, but anyway thanks for linking the other questions. I will give them a look. $\endgroup$ May 15 at 7:44
  • 2
    $\begingroup$ @timtombobjohn then change the title of your post... $\endgroup$ May 15 at 8:21

1 Answer 1


Maurice Herlihy, Dmitry Kozlov and Sergio Rajsbaum, "Distributed Computing Through Combinatorial Topology", 2014


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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