<ul>
<li><p><a href="http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/S0273-0979-08-01176-2.pdf" rel="nofollow noreferrer">Matrix multiplication</a> (References in there)</p>
</li>
<li><p><a href="http://crypto.stanford.edu/%7Edabo/papers/mlinear.pdf" rel="nofollow noreferrer">Pairing based cryptography</a></p>
<p>Focuses on what one can do with certain hypothetical multilinear pairings. The conjecture is they don't exist within Algebraic Geometry. If you prove otherwise, may be you can give a talk at the next ICM</p>
</li>
<li><p><a href="http://web.archive.org/web/20071118132425/http://math.mit.edu/%7Ekedlaya/18.787/intro.pdf" rel="nofollow noreferrer">&quot;Explicit&quot; etale cohomology</a> and <a href="http://www.math.u-bordeaux1.fr/%7Ejcouveig/book.htm" rel="nofollow noreferrer">Computations in Arithmetic Geometry</a>
(The book actually works with explicit etale cohomology)</p>
</li>
<li><p>Computationally resolving singularities of algebraic varieties.</p>
</li>
<li><p><a href="http://www.math.umass.edu/%7Ehajir/m499c/tvn-book.pdf" rel="nofollow noreferrer">Tsfasman-Manin's book</a> and Sudan-Guruswami List decoding work on algebraic-geometric aspects of coding theory.</p>
</li>
</ul>

CC BY-SA 3.0
2011-09-06T19:33:25.770Z
The work of Sudan and Guruswami is mostly devoted to list decoding (which, well, concerns AG codes as well) — topic that raised at the end of 90-s and was heavily developed at 2000-s. The algebraic geometry method appeared at 80-s in papers by Goppa, and was developed by Tsfasman and Vladutc and many others at 90-s. Personally I would suggest the paper: Hoholdt, van Lint, Pellikaan, Algebraic geometry codes, 1998.
Artem Pelenitsyn
CC BY-SA 3.0
2011-09-06T19:37:20.260Z
As for computational AG I would suggest books by Cox—Little—O'Shea and Schenck, but this topic is a bit irrelevant to the “connection from computational complexity to algebraic geometry” which was requested by Joshua.
Artem Pelenitsyn
CC BY-SA 3.0
2011-08-25T13:25:11.757Z
Is this an explicit example of etale cohomology? http://www.math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
CC BY-SA 3.0
2011-08-25T16:35:32.343Z
Please refer here. http://www-math.mit.edu/~kedlaya/18.787/intro.pdf
v s
CC BY-SA 4.0
2024-07-09T13:00:32.593Z
Just wanted to point out that Kedlaya's writing is on rigid (p-adic) cohomology, which is different from the etale ($\ell$-adic) cohomology. It seems hard to make the latter explicit.
Zeyu
CC BY-SA 3.0
2011-08-25T06:09:37.987Z
2015-11-15T17:35:17.787Z
2020-06-17T09:38:08.363Z
v s
<p>In <a href="http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf" rel="nofollow">Slide 26</a>, Martin Escardo provides an algorithm that might give you what you're looking for:</p>

<ol>
<li>Go the library.</li>
<li>Pick a book on topology.</li>
<li>Pick a theorem.</li>
<li>Apply the dictionary.</li>
<li>Get a theorem in computation.</li>
</ol>

<p><a href="http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf" rel="nofollow">http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf</a></p>

<p>See also <a href="http://www.cs.bham.ac.uk/~mhe/papers/exhaustive.pdf" rel="nofollow">this paper</a></p>

CC BY-SA 3.0
2015-11-16T23:14:55.430Z
The dictionary being a correspondence between terms in topology (like open set) and computability (like semi-decidable set).
Mitch
CC BY-SA 3.0
2015-12-11T19:44:14.497Z
maybe this should be the accepted answer
Nikos M.
CC BY-SA 3.0
2015-12-12T01:11:44.333Z
@NikosM. I would be torn with the first answer and this one and the accepted answer has been accepted for awhile so I rather not change it. If there was a merged answer with everything maybe but then this question would probably become a community wiki.
Joshua Herman
CC BY-SA 3.0
2015-12-12T11:05:42.893Z
@JoshuaHerman, sure i understand, although myself have sometimes changed the accepted answer as my knowledge updated and another answer more to the point of the question appeared. Anyway, about the topic, you will find out that there are many more analogies with other areas of mathematics as well (i,e not only between topology-complexity) For example, an area which has this potential (and was inspired by topology) is category theory
Nikos M.
CC BY-SA 3.0
2015-11-16T19:07:09.667Z
2015-11-16T19:07:09.667Z
NietzscheanAI
<p>Some recent references here from Algebraic Topology, and UGC hardness- <a href="https://arxiv.org/pdf/1801.08380.pdf" rel="nofollow noreferrer"> Morse Theory </a>, and another reference <a href="https://arxiv.org/abs/1803.06800" rel="nofollow noreferrer"> Unique Games Conjecture and Computational Topology </a>. 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. </p>

CC BY-SA 3.0
2018-04-29T01:08:13.497Z
2018-04-29T01:08:13.497Z
user3483902
<p>As background, you should definitely study <a href="http://dl.acm.org/citation.cfm?id=808735">Ben-Or's work on lower bounds</a>, as well as <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.4061">Mulmuley's P vs NC paper</a>. </p>

CC BY-SA 3.0
2011-08-24T21:43:25.177Z
2011-08-27T16:01:02.303Z
2011-08-27T16:01:02.303Z
Suresh Venkat
<p>I was wondering what papers I should read to understand this question</p>

<blockquote>
  <p>A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of mathematics not yet developed. Perhaps someone will develop a whole new direction for mathematics in order to handle the P versus NP question.
  -From <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.489&amp;rep=rep1&amp;type=pdf">Fortnow 2002</a></p>
</blockquote>

<p>Another phrasing of the question would be "What papers should I read to create a connection from computational complexity to algebraic geometry / topology?"</p>

<p>I have looked at <a href="http://arxiv.org/abs/0908.1936">Geometric Complexity Theory</a> already . Also papers in Topological Quantum Computation which I have read enough papers that I am already familiar with the field. Am I missing anything?</p>

CC BY-SA 3.0
2011-08-24T21:39:32.250Z
May I suggest a change to the title? Something like "Papers on relation between computational Complexity and algebraic geometry/topology".
Kaveh
CC BY-SA 3.0
2011-08-25T07:25:54.777Z
Could you elaborate your question a bit? I would think everyone would miss something from that line if that line is true since he is talking about "unknowns". I think professor Suresh's answer below on lower bounds is a good reference.
v s
CC BY-SA 3.0
2011-08-25T07:37:22.343Z
You may also want to look into this related question: http://cstheory.stackexchange.com/questions/2898/applications-of-topology-to-computer-science
Martin Schwarz
CC BY-SA 3.0
2011-08-26T11:03:15.380Z
I also found this paper http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman
<cc.complexity-theory><reference-request><gct><algebraic-topology>
Papers on relation between computational complexity and algebraic geometry/topology?
Joshua Herman
# Papers on relation between computational complexity and algebraic geometry/topology?

(Asked by: username_0 on 2011-08-24)

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 mathematics not yet developed. Perhaps someone will develop a whole new direction for mathematics in order to handle the P versus NP question.
> -From [Fortnow 2002](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.489&rep=rep1&type=pdf)

Another phrasing of the question would be "What papers should I read to create a connection from computational complexity to algebraic geometry / topology?"

I have looked at [Geometric Complexity Theory](http://arxiv.org/abs/0908.1936) already . Also papers in Topological Quantum Computation which I have read enough papers that I am already familiar with the field. Am I missing anything?

**Tags:** cc.complexity-theory, reference-request, gct, algebraic-topology

> **Comments:**
> **username_1**: May I suggest a change to the title? Something like "Papers on relation between computational Complexity and algebraic geometry/topology".  
> **username_2**: Could you elaborate your question a bit? I would think everyone would miss something from that line if that line is true since he is talking about "unknowns". I think professor Suresh's answer below on lower bounds is a good reference.  
> **username_3**: You may also want to look into this related question: http://cstheory.stackexchange.com/questions/2898/applications-of-topology-to-computer-science  
> **username_0**: I also found this paper http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf  

---

## 4 answers

### Answer by username_10 on 2011-08-24. Score: 14 | Accepted answer

As background, you should definitely study [Ben-Or's work on lower bounds](http://dl.acm.org/citation.cfm?id=808735), as well as [Mulmuley's P vs NC paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.4061).


---

### Answer by username_2 on 2011-08-25. Score: 11

* [Matrix multiplication](http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/S0273-0979-08-01176-2.pdf) (References in there)
* [Pairing based cryptography](http://crypto.stanford.edu/%7Edabo/papers/mlinear.pdf)

  Focuses on what one can do with certain hypothetical multilinear pairings. The conjecture is they don't exist within Algebraic Geometry. If you prove otherwise, may be you can give a talk at the next ICM
* ["Explicit" etale cohomology](http://web.archive.org/web/20071118132425/http://math.mit.edu/%7Ekedlaya/18.787/intro.pdf) and [Computations in Arithmetic Geometry](http://www.math.u-bordeaux1.fr/%7Ejcouveig/book.htm)
  (The book actually works with explicit etale cohomology)
* Computationally resolving singularities of algebraic varieties.
* [Tsfasman-Manin's book](http://www.math.umass.edu/%7Ehajir/m499c/tvn-book.pdf) and Sudan-Guruswami List decoding work on algebraic-geometric aspects of coding theory.

> **Comments:**
> **username_0**: Is this an explicit example of etale cohomology? http://www.math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf  
> **username_2**: Please refer here. http://www-math.mit.edu/~kedlaya/18.787/intro.pdf  
> **username_4**: The work of Sudan and Guruswami is mostly devoted to list decoding (which, well, concerns AG codes as well) — topic that raised at the end of 90-s and was heavily developed at 2000-s. The algebraic geometry method appeared at 80-s in papers by Goppa, and was developed by Tsfasman and Vladutc and many others at 90-s. Personally I would suggest the paper: Hoholdt, van Lint, Pellikaan, Algebraic geometry codes, 1998.  
> **username_4**: As for computational AG I would suggest books by Cox—Little—O'Shea and Schenck, but this topic is a bit irrelevant to the “connection from computational complexity to algebraic geometry” which was requested by Joshua.  
> **username_5**: Just wanted to point out that Kedlaya's writing is on rigid (p-adic) cohomology, which is different from the etale ($\ell$-adic) cohomology. It seems hard to make the latter explicit.  

---

### Answer by username_6 on 2015-11-16. Score: 4

In [Slide 26](http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf), Martin Escardo provides an algorithm that might give you what you're looking for:

1. Go the library.
2. Pick a book on topology.
3. Pick a theorem.
4. Apply the dictionary.
5. Get a theorem in computation.

<http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf>

See also [this paper](http://www.cs.bham.ac.uk/~mhe/papers/exhaustive.pdf)

> **Comments:**
> **username_7**: The dictionary being a correspondence between terms in topology (like open set) and computability (like semi-decidable set).  
> **username_8**: maybe this should be the accepted answer  
> **username_0**: @NikosM. I would be torn with the first answer and this one and the accepted answer has been accepted for awhile so I rather not change it. If there was a merged answer with everything maybe but then this question would probably become a community wiki.  
> **username_8**: @JoshuaHerman, sure i understand, although myself have sometimes changed the accepted answer as my knowledge updated and another answer more to the point of the question appeared. Anyway, about the topic, you will find out that there are many more analogies with other areas of mathematics as well (i,e not only between topology-complexity) For example, an area which has this potential (and was inspired by topology) is category theory  

---

### Answer by username_9 on 2018-04-29. Score: 4

Some recent references here from Algebraic Topology, and UGC hardness-  [Morse Theory](https://arxiv.org/pdf/1801.08380.pdf) , and another reference  [Unique Games Conjecture and Computational Topology](https://arxiv.org/abs/1803.06800) . 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.


---

