<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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. <a href="https://www.wiley.com/en-us/Theory+of+Computational+Complexity,+2nd+Edition-p-9781118306086" rel="nofollow noreferrer">Du &amp; Ko's book</a> and <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/" rel="nofollow noreferrer">Erik's lower bounds course</a> are my choice so far.</p>
<p>Do you have any feedback or comments? Do you think I am on right pathway? Do you have alternative approaches?</p>
<p>P.S. Send me a direct message if you wish to join me self-studying, Even if your interest is in general TCS.</p>

CC BY-SA 4.0
2022-03-05T15:15:42.500Z
Avi Wigderson's book https://www.math.ias.edu/avi/book may also be interesting to look at.
Chandra Chekuri
CC BY-SA 4.0
2022-03-05T17:53:40.653Z
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?
Mostafa Touny
<cc.complexity-theory><ds.algorithms><advice-request>
Accessible entry for computational complexity theory through concrete problems
Mostafa Touny
# Accessible entry for computational complexity theory through concrete problems

(Asked by: username_0 on 2022-03-04)

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](https://www.wiley.com/en-us/Theory+of+Computational+Complexity,+2nd+Edition-p-9781118306086) and [Erik's lower bounds course](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/) 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.

**Tags:** cc.complexity-theory, ds.algorithms, advice-request

> **Comments:**
> **username_1**: Avi Wigderson's book https://www.math.ias.edu/avi/book may also be interesting to look at.  
> **username_0**: 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?  

---

## 0 answers

