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.
15
questions
9
votes
1
answer
240
views
algebraic topology in distributed computing
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 ...
- 101
4
votes
1
answer
141
views
High-dimensional expanders through the lens of algebraic topology
High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
- 43
6
votes
0
answers
122
views
Enumerating homologies of disjoint paths
I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths.
I did not understand how do they re-route the paths through a spanning tree and ...
- 191
3
votes
0
answers
109
views
Homologous flows on planar graphs
I was reading this paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs".
First they describe what are cohomologous functions on a graph. My interpretation of this definition ...
- 191
14
votes
1
answer
525
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-...
- 1,049
10
votes
2
answers
859
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 ...
- 101
23
votes
1
answer
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 ...
- 1,661
10
votes
2
answers
413
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 ...
- 2,294
-5
votes
1
answer
286
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 ...
- 1,292
4
votes
1
answer
154
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....
- 367
5
votes
3
answers
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
2
answers
536
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 ...
- 1,311
17
votes
1
answer
2k
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 ...
- 10.6k
23
votes
4
answers
4k
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 ...
- 1,661
7
votes
0
answers
161
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 ...
- 32.8k