Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algebraic-topology]

Algebraic topology is the study of objects under continuous deformation using tools from abstract algebra such as groups, fields , rings and algebras (a combination of a group and a ring). An example is the Temperley–Lieb algebra to study braids in knot theory.

13
votes
0answers
252 views

Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings... From the ad-...
10
votes
2answers
553 views

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

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 ...
23
votes
2answers
2k views

Knot Recognition as a Proof of Work

Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion. Is it possible to use a Decision problem ...
10
votes
2answers
228 views

The complexity of finding a Borsuk-Ulam point

The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$. Simmons and Su (2002) describe a method ...
-5
votes
1answer
226 views

Some questions (still) unresolved about braids?

I was looking for interesting questions pertaining to braid theory. I don't know if the following are considered important, but I'd like to ask: (1) in relation with the following link, is it true ...
4
votes
1answer
134 views

Generalizations of planar graphs that include hypercubes with large side length in $R^d$

A lot of people have asked about generalizations of planar graphs on other forums. Some topics include: https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs https://math....
5
votes
3answers
1k views

How to measure programming language succinctness?

I want to explore the notion of quantifying the amount of succinctness a programming language provides. That is, the amount a high-level language reduces the complex. This idea of "simplification" ...
14
votes
2answers
434 views

Approaches to GI inspired by knot problem

GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to ...
15
votes
1answer
1k views

Forbidden minors for bounded genus graphs

It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs ...
19
votes
4answers
2k views

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

I was wondering what papers I should read to understand this question A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of ...
7
votes
0answers
142 views

Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?

In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...