7

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 designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic. In more detail, as is well known in the Graph Non ...


5

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence". His formulation of the problem is: Borsuk-Ulam. Given an integer n and a Turing machine computing for each point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\...


4

How is the oracle given and what do we know about $g$? If the oracle is black-box and we only know that $g$ is continuous odd, then already for $n=1$ we might require infinitely many questions... If the oracle is given by some Turing-machine, then you get that your problem is FIXP-complete, PPAD-complete, where the size of the input is length of $\epsilon$...


4

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 of graphs, and "lifting" of graphs, and could point to a deeper link between Topology, and the Unique Games Conjecture.


4

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 computation. http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf See also this paper


3

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


3

You may want to look at nowhere dense graphs. http://www.sciencedirect.com/science/article/pii/S0195669811000151 One of the reasons why minor-closedness is natural is the following. We typically want to work with families of graphs rather than specific graphs. And we want to solve problems with arbitrary weights/capacities on edges/nodes. Suppose we want to ...


3

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 approach to scaling such analyses is modularity which allows decomposing the problem into sub-problems. Indeed this usually consists in identifying cycle-like ...


2

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


1

the Rosetta Code repository has been used for a new comprehensive scientific/ academic study of language succinctness among other comparisons of properties. announced at "Analyzing Programming Languages using Rosetta Code" A Comparative Study of Programming Languages in Rosetta Code Nanz/ Furia Sometimes debates on programming languages are more ...


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