I turn sixty today, spending my birthday reviewing a computer science department in Asia. Sixty is a good time to look back and reflect in a rambling way.
I started grad school in 1985. The P v NP problem was only 14 years old when I started. 38 years later we are no closer to solving it.
Nevertheless the field of computational complexity has remained strong, producing exciting research nearly every year. We're not seeing the surprising results that we saw through the early 90s but we've gained a much better understanding of pseudorandomness, coding theory, proof complexity, communication complexity, quantum complexity and circuit complexity (to an extent). The hard problems remain hard but that hasn't hampered progress in the field.
The field hasn't grown as dramatically as some others in theoretical computer science but neither has it shrunk. We have many great young researchers coming up in the field and its future is secure for decades to come.
I have some regrets for the field. Computational complexity has moved more towards mathematics with a focus on technical difficulty over conceptual novelty. We were quick to pick up on probabilistic, parallel and quantum computing, much slower on the cloud and machine learning. Combinatorial optimization has gotten extremely good, we can solve many NP-complete problems in practice, a point we rarely acknowledge.
For myself, I had an active research career for a good two decades. But then the field moved, away from my strength in the structure of complexity classes and more towards more combinatorial, algebraic and analytic techniques. A field should evolve but I found it difficult to keep up. So I focused on this blog, wrote a book, took on larger leadership and administrative roles. I try to follow what's going on in the field, but I'm happy to leave the research to the next generations, especially to my former students, several of whom have become leaders in the field themselves.
Someone recently asked me if I have regrets in my research career. I said that I’ve lived through some incredible advances in computing, but my research has played no significant role in any of it.
Nevertheless as the computing world, if not the world as a whole, continually gets more complex, computational complexity has a continual mission to make sense of it. And so we shall.
Thanks for your candor in assessing your own time in the research world and the difficulty of keeping up as the field moves fast. Not enough people talk about this phenomenon. It would be great to have more discussion about how this affects people and what one should do to cope and adapt and meaningfully contribute.
ReplyDeleteHey! Happy birthday, you whippersnapper! (I turned 71 last month).
ReplyDeleteFirst of all, thanks for the blog!
But hey, guy, 60 really is young. I'm way older than that, and I'm looking forward to doing a whole bunch more. Of course, I have it easy: I'm a professional dilettante, and only aspire to scratching the top 10% of things, not the top 1%.
FWIW, when I was your age, I was playing in a jazz big band where I was the youngest member. The bandleader had this trick: when there was a gig that actually paid money, he'd kick out most of the amateurs and bring in retired pros from the early postwar period. (I was the only guitarist around, so I got to play. It was a joy and an honor.) They.Were.Good. But they were all over 80, so while their music was still great, they were slowing down physically.
So you've got another 20 years to kick arse, and then a lot more time to enjoy what you've learned/achieved. Keep at it!
Happy birthday Lance! I very much agree with "Computational complexity has moved more towards mathematics with a focus on technical difficulty over conceptual novelty." Particularly, thanks a lot for your blog.
ReplyDeleteKind regards, Arne
Happy bday Lance!
ReplyDeleteThanks for the moving post! But I strongly disagree with the statement about no significant role. Wouldn’t you agree LFKN by itself revolutionised the field?
ReplyDeleteCongratulations for your Birthday! I hope I hear from this blog as long as I turn sixty.
ReplyDeleteHappy birthday Lance. This is another nice article in this blog, with insights, self-reflection, and optimism. I look forward to hearing more from here.
ReplyDeleteLance, your (and Bill's) blog was incredibly influential to me as an undergrad and grad student (2009-ish to mid 2010's). It got me excited about doing complexity theory and now I get to think about complexity theory for a living, which I feel blessed and lucky for.
ReplyDeleteAlso, I think you're underselling your research impact. Let me highlight the fact that BFL set in motion PCPs and IP = PSPACE. These in turn are driving the zero-knowledge SNARK revolution in block chains. I think we have yet to see the most exciting uses of IPs and MIPs in the decades to come. It just takes a while for people to catch on.
This might seem odd to say as a one person anon, but on behalf of the TCS community wishing you all the very best, in health and happiness, and a huge thank you and Bill for keeping up the blog.
ReplyDeleteHappy Birthday! And as for "no significant role", I do discuss some of your writings many times in my book (Philosophy of Computer Science)!
ReplyDeleteHappy birthday Lance! FWIW, I also feel like I'm getting old and have more and more trouble keeping up.
ReplyDeleteHappy birthday and thanks for the candid post. I think one key to a long and productive research career is to change your research topic from time to time. Otherwise, even your favorite topic can become boring and you run out of new ideas.
ReplyDelete