In 1994, the FST&TCS conference invited me to give a talk at their meeting in Madras (now Chennai). I was in my tenth year as a complexity theorists since I started graduate school and looked back at a very impressive decade in computational complexity. So for the talk and corresponding paper (PDF) I went through my favorite ten theorems from 1985-1994, and used them to describe progress in a slew of subareas of complexity.
In 2002 I started this blog and in 2004 decided to repeat the exercise for the following decade, and again in 2014. I also went back through my favorite theorems from the early days of complexity, 1965-1974 and 1975-1984.
It's 2024 and as I approach my fortieth year in complexity, it's time once again a time to look back through the sixth decade of the field, still producing amazing results in a now mature field. I'll announce one theorem a month from February through November with a wrap-up in December. The choices are mine though feel free to send me your nominees. I choose theorems not based on technical depth but on how they change the way we think about complexity with an eye towards hitting may different subareas of the field.
See you in February where we'll go back to 2015 for a theorem decades in the making.
1. The upcoming February post should not be an ALGORITHM as many of us may guess. That would not be a complexity result. Computational complexity books certainly NEVER include the proofs of that algorithmic result.
ReplyDeleteOtherwise, group theory book is a more appropriate name for that.
2. "The choices are mine through feel free to send me your nominees."
through --> though
2. Fixed the typo. 1. Don't get ahead of the game.
DeleteWonderful post! Could you give some advice on how to study complexity theory on one's own, and/or to follow the research frontier (other than reading this amazing blog), 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 (certainly this blog has provided some useful lists!)? How hard is it to follow all the important results (Is this even possible/necessary)? How would you determine whether a new paper is worth reading in full details? Thank you!
ReplyDeleteGood question but too long for a comment. Let me address in a future post.
DeleteThank you and looking forward to the future post. Of course the short answer is to go to graduate school, and my question is mainly for those who don't have the luxury, partially motivated by [’t Hooft](https://goodtheorist.science/) and [Susskind](https://theoreticalminimum.com/biography) on physics. Not necessarily a whole program but any suggestion on complexity theory would be greatly appreciated!
Delete