Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

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

2 Answers

up vote 10 down vote accepted

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

share|improve this answer
add comment
share|improve this answer
Is this an explicit example of etale cohomology? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf –  Joshua Herman Aug 25 '11 at 13:25
Please refer here. www-math.mit.edu/~kedlaya/18.787/intro.pdf –  v s Aug 25 '11 at 16:35
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 Sep 6 '11 at 19:33
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 Sep 6 '11 at 19:37
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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