Skip to main content
8 votes

Knot Recognition as a Proof of Work

If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be ...
Mark S's user avatar
  • 1,125
4 votes

Papers on relation between computational complexity and algebraic geometry/topology?

Some recent references here from Algebraic Topology, and UGC hardness- Morse Theory , and another reference Unique Games Conjecture and Computational Topology . The latter is about covering spaces ...
user3483902's user avatar
  • 1,261
3 votes

What are some interesting applications of homotopical algebra in theoretical computer science?

Two big applications of homotopy theory in theoretical computer science are Homotopy Type Theory revealed a completely unexpected connection between the theory of the typed lambda calculus and ...
Neel Krishnaswami's user avatar
3 votes
Accepted

Algebraic topology for termination proofs

As someone somewhat familiar with termination analysis, I'd say that the techniques are only as ad-hoc as the programs they aim to prove termination of, which is to say very ad-hoc indeed. The crucial ...
cody's user avatar
  • 13.9k
2 votes

What are some interesting applications of homotopical algebra in theoretical computer science?

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: ...
hengxin's user avatar
  • 2,329
2 votes
Accepted

High-dimensional expanders through the lens of algebraic topology

High-dimensional expanders come in several flavors. The most common ones in TCS are spectral expanders, coboundary expanders, and cosystolic expanders. The latter two are defined using the algebraic ...
Yuval Filmus's user avatar
  • 14.5k
1 vote

algebraic topology in distributed computing

Maurice Herlihy, Dmitry Kozlov and Sergio Rajsbaum, "Distributed Computing Through Combinatorial Topology", 2014
Kaveh's user avatar
  • 21.7k

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