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 ...
- 1,063
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 ...
- 1,181
4
votes
Papers on relation between computational complexity and algebraic geometry/topology?
In Slide 26, Martin Escardo provides an algorithm that might give you what you're looking for:
Go the library.
Pick a book on topology.
Pick a theorem.
Apply the dictionary.
Get a theorem in ...
- 773
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 ...
- 13.7k
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 ...
- 32.4k
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 ...
- 14.3k
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:
...
- 2,329
Only top scored, non community-wiki answers of a minimum length are eligible