23
$\begingroup$

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

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ May I suggest a change to the title? Something like "Papers on relation between computational Complexity and algebraic geometry/topology". $\endgroup$
    – Kaveh
    Aug 24, 2011 at 21:39
  • $\begingroup$ 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. $\endgroup$
    – v s
    Aug 25, 2011 at 7:25
  • 2
    $\begingroup$ You may also want to look into this related question: cstheory.stackexchange.com/questions/2898/… $\endgroup$
    – Martin Schwarz
    Aug 25, 2011 at 7:37
  • 1
    $\begingroup$ I also found this paper cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf $\endgroup$
    – Joshua Herman
    Aug 26, 2011 at 11:03

4 Answers 4

Reset to default
13
$\begingroup$

As background, you should definitely study Ben-Or's work on lower bounds, as well as Mulmuley's P vs NC paper.

Improve this answer
$\endgroup$
10
$\begingroup$
Improve this answer
$\endgroup$
4
  • $\begingroup$ Is this an explicit example of etale cohomology? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf $\endgroup$
    – Joshua Herman
    Aug 25, 2011 at 13:25
  • $\begingroup$ Please refer here. www-math.mit.edu/~kedlaya/18.787/intro.pdf $\endgroup$
    – v s
    Aug 25, 2011 at 16:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Artem Pelenitsyn
    Sep 6, 2011 at 19:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Artem Pelenitsyn
    Sep 6, 2011 at 19:37
4
$\begingroup$

In Slide 26, 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

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ The dictionary being a correspondence between terms in topology (like open set) and computability (like semi-decidable set). $\endgroup$
    – Mitch
    Nov 16, 2015 at 23:14
  • $\begingroup$ maybe this should be the accepted answer $\endgroup$
    – Nikos M.
    Dec 11, 2015 at 19:44
  • $\begingroup$ @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. $\endgroup$
    – Joshua Herman
    Dec 12, 2015 at 1:11
  • $\begingroup$ @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 $\endgroup$
    – Nikos M.
    Dec 12, 2015 at 11:05
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.