I am planning to start studying computational complexity theory. As the field is technical for a fresh undergrad alumni like me, I thought a good approach is to tackle it through areas I am more familiar with.

I read Sipser's and saw couple of lectures and conferences workshops; Barak's book seems to endorse intuitive proofs; Other books are very technical for me.

While I am already building up my math toolboxes, it seems a good idea to enter computational complexity theory early even if my contribution is a very special case.

Particularly, I thought of studying notable concrete problems, alongside related math techniques and algorithms. For example SAT and its solvers. Training on reductions should also be an accessible entry for establishing relationships between different complexity classes. Defining a genre of problems by a common theme or property among them might be a good training also. Du & Ko's book and Erik's lower bounds course are my choice so far.

Do you have any feedback or comments? Do you think I am on right pathway? Do you have alternative approaches?

P.S. Send me a direct message if you wish to join me self-studying, Even if your interest is in general TCS.

  • 1
    $\begingroup$ Avi Wigderson's book math.ias.edu/avi/book may also be interesting to look at. $\endgroup$ Mar 5 at 15:15
  • $\begingroup$ Thanks for the recommendation, Chandra. Would you clarify what distinguishes Avi's book from other resources? When or for which purpose would you use it? $\endgroup$ Mar 5 at 17:53


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.