Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the journal 12 years ago!

I was wondering if by now this work has already gone into some textbook or has it gotten improved or if there are already pedagogic expositions available for this? It would be helpful to get such references if they exist!

  • 1
    $\begingroup$ Please state exactly which result you want an exposition for. See Jan Krajicek's book "Forcing with Random Variables", chapters related to proof complexity generators. Razborov himself has links to some good surveys on the topic on his homepage. $\endgroup$
    – Kaveh
    Sep 29 '16 at 1:22
  • $\begingroup$ ^These subsume this particular paper? $\endgroup$
    – Anirbit
    Sep 29 '16 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.