Learning Complexity on Your Own
Computational Complexity 2024-01-24
Could you give some advice on how to study complexity theory on one's own, and/or to follow the research frontier even to find one's own research topic, for someone with solid math and TCS background (say somewhere between Sipser and Arora & Barak), nonetheless an outsider? For example, what books/papers to read? How hard is it to follow all the important results? How would you determine whether a new paper is worth reading in full details?
Let me suggest a backwards approach. Find interesting papers, by checking the latest proceedings in major conferences such as STOC, FOCS and Computational Complexity or those mentioned on blogs or Qaunta. If you don't have access to the papers you can often find them on author's home pages or on arXiv or ECCC. First look at titles that interest you, then read the abstract, intro and the full paper. If you lose interest go on to another paper.
Once you find a paper that excites you, start reading in details. When you find terms or references to old results you don't know, go do some research, either the cited papers or sites like the Complexity Zoo, Wikipedia and TCS Stack Exchange. You can also find videos and lecture notes on various topics. Large language models like ChatGPT can help understand concepts but have a healthy skepticism on what it says, particularly on specialized material.
As your read the cited papers, repeat the process. You basically doing a depth-first search through the literature. If you do this for a paper like Ryan Williams' NEXP is not in ACC\(^0\), you'll get a pretty well-rounded education in complexity.