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 Quanta. 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.
(Bill) Starting with STOC/FOCS/COMPLEXITY papers might be too hard- though you DO say to goto references. However, I would say its better to start with a textbooks like Arora-Barack or Goldreich, or something more specialized like Comm. Comp. by
ReplyDeleteKushlevitz-Nisan or by Rao-Yehudayoff. OH- also, read book REVIEWS to see which BOOKS you might want to read. My homepage has a pointer to a webapge of around 20 years of book reviews for SIGACT NEWS. Jut google gasarch
Qaunta -> Quanta (presumably plural of quantum)
ReplyDeleteThanks. Fixed.
Delete(Comment is too long, so I am sending it in two parts.)
ReplyDelete1--- Hi,
I had to do a similar thing on my own last year, as I switched from physics to TCS. FWIW, I also started my PhD without having taken any CS courses during my BSc, but a solid math background helps.
I will share a part of my experience re: how I started to learn complexity theory on my own, but before doing so, I would like to tell you that --put aside the words by 't Hooft and Susskind-- at least in my opinion, graduate school resources are uniquely efficient in providing robust learning, especially if you want to follow frontier research in a quickly evolving field like complexity theory.
I did self-learning mostly because I was too impatient to wait for the semester during which the department would offer the usual graduate complexity course, however, I believe this self-learning process wouldn't be so efficacious if I hadn't had regular discussions on complexity theory with my advisors and mentors. So, given what you wrote, even if you cannot currently be a part of a graduate program, I hope you can find some people around you whom you can have discussions with on the material you are learning.
OK, so, my first step in self-learning/teaching complexity theory consisted of grabbing the following books from the library:
1) Computational Complexity: A Modern Approach by Boaz Barak and Sanjeev Arora
2) The Nature of Computation by Cristopher Moore and Stephan Mertens
3) Boolean Function Complexity by Stasys Jukna
4) Mathematics and Computation by Avi Wigderson
1) gives a panoramic view, solving the exercises would help you greatly in establishing both a general understanding and also a meta-understanding of complexity theory (by the latter, I mean, you will develop a sense of smell, “what kind of mathematical techniques are used in solving what kind of problems?” (e.g., for lower bounds, class separation proofs). 2) provides immense intuition on certain topics involving randomness and quantum complexity theory; 3) is a personal favorite for circuit complexity theory and as rigorous as it gets; 4) is a book that I kept for months (IMO, it is not a book to be devoured suddenly by a neophyte, but you can take small bites at it for months and then it will pay off). Computational Complexity: A Conceptual Perspective by Oded Goldreich is also a great resource, but I wasn't able to delve into it before I was already comfortable with the basics.
Especially in circuit complexity theory, when I had trouble understanding what Jukna wrote, watching some lecture videos on the subject helped me, e.g., those you can find on Ryan O'Donnell's Youtube channel. I also used TCS stackexchange for my questions almost every day, and glanced at lecture notes by Luca Trevisan (Berkeley notes) and Ryan O'Donnell.
If you are interested, I think it is certainly better to start learning communication complexity on top of a generic computational complexity background. I liked the book by Amir Yehudayoff and Anup Rao the most, and Toni Pitassi's lecture notes always contain interesting remarks and pointers.
Part 2--- In addition to the above, what made (especially) circuit complexity “click” for me was seeing different approaches --different algebraic / analytical / combinatorial techniques-- employed in solving a given problem, such as proving a lower bound (prove in as many as ways possible that Parity cannot be computed by AC^0 circuits). [As George Pólya said, and this must be true in particular when it comes to grasping why some functions are harder than others... “It is better to solve one problem five different ways, than to solve five problems one way”.]
ReplyDeleteIn this regard, I am really grateful that I came across Ryan O'Donnell's book, “Analysis of Boolean Functions”. Among the books I studied, it is without doubt the greatest catalyst which assisted my learning process. Having analytical techniques under your belt will make it absolutely easier for you to follow recent research progress in complexity theory. Same goes for combinatorial techniques -- you might familiarize yourself with them by studying Jukna's book on Extremal Combinatorics (sunflowers are quite popular nowadays), and Yufei Zhao's MITOCW lecture notes on probabilistic methods.
And beyond the books -- I also watched a lot of recorded talks on Youtube (TCS+, Simons Foundation, Princeton IAS, etc.); I think hundreds of them before I started to really understand what was going on. In the short run, this exposed me to the terminology, and soon enough I was able to connect some dots. And eventually this helped me sample the research landscape to get a better sense of what I am *particularly* interested in complexity theory. It goes without saying but it also helps greatly if you try to read as many papers as you can, and read some of them as many times as you can. And you probably already know this, but seeing whether you can succinctly explain to yourself what is done in the “original” papers which produced the results you encountered in books is another good way to test whether you actually understand what you studied. It might not be true for every field that its original / classical papers are reader-friendly (trying to read a solid state paper from the 60s were excruciating for some people I know) but in TCS I find it extremely refreshing to go through classical papers.
It is like learning a new language, and so there is no linear way of making it work, but I hope you have lots of fun; this is truly one of the most beautiful fields to be in.
PS. This blog and Scott Aaronson's blog also gave me insights on the road, so thanks!