I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll down that page and you'll see the rather strong collection of participants that are spending much of the fall at the Institute.
I purposely chose a week without a workshop--I'd rather talk to people than sit in talks. My former PhD student Rahul Santhanam is hosting me and we are having some fun discussions about the minimum circuit-size problems, pseudorandom generators and white vs black box algorithms. I've grown a little rusty in complexity during my years as department chair and have to work to keep up with Rahul. The student has become the master.
Even a quiet week at Simons is not that quiet. Every night seems to have a theme: trivia, board games, pub night, music night. I participated in a discussion with the "journalist in residence" on how to make lower bounds interesting to the general public. As part of a Turing awardee lecture series, Andy Yao gave a talk on Game Theory in Auction and Blockchain which included some reminiscing of Yao's golden time in Berkeley back in the early 80's when he helped lay the mathematical foundations of modern cryptography.
Simons started as a competition and, while I was on team Chicago, I have to admit Berkeley has done a wonderful job with the institute. We've just seen the results from another competition, with Amazon splitting their "second headquarters" between Northern Virginia and Queens, missing an awesome opportunity in Atlanta (not that I'm biased). Not surprised about the DC area, but pretty surprised about separating the HQ into two locations, neither planned to reach the level of activity of HQ1 in Seattle. Amazon stated that they didn't think they could find the tech talent to fill 50,000 positions in a single city. So much for "build it and they will come".
1) I think its impossible to make lower bounds interesting to the general reader. People can sort-of-understand `there is a BETTER way to do X!' but have a hard time with `you can't do better than X'. but see
ReplyDeletenext point.
2) Crypto may be the only area where lower bounds can be explained to the pubic in terms of `Eve CANNOT crack this code. Until she does.
3) ``Golden time''- people living in a golden era usually don't know it. Perhaps we are in one now!
Lance the sociopath-wannabee!!!
ReplyDeleteNobody sees you praising your peers. Clearly you must need something out of Rahul that you aren't getting yet.
Please this is so transparently nakedly self-serving that Kissinger might die in a diabetes attack.