Last year I had a great sabbatical at Harvard university, and this semester, thanks to the flexibility of the NEU administration, I am at the Simons institute in Berkeley for their program on fine-grained algorithms and complexity. The institute is amazing, and there is an avalanche of interesting talks which is overwhelming, even by Boston standards.
As with all great things, one can wonder if the institute could be made even better. Here are two small thoughts about this. The first is about housing. I think it would be nice to have a block of houses managed by the institute. And I think I would think so even if my experience with finding housing hadn’t been what it has been. The starting point is that I could not find anything that suited me. Whatever the reason for this, it was definitely *not* because of lack of support from the institute. At some point a good listing did come out, and I immediately grabbed it, but after a long exchange the landlord changed their mind. By that time it was very late in the game, and it was harder to find anything. Since I was about to spend more time looking for an apartment than actually living there, I decided to go all-out and pay a rent that is ridiculous even for someone who rented in New York city. Naturally, I ended up in a terrible place. For one thing, I happen to disagree with the landlord’s calculation that a human being needs less than 100 square feet to survive. Shame on me for not inquiring about the size of the unit. So, even if the market looked completely hopeless, I had to get back into it. Here again the institute’s staff was extremely supportive, and in a reversal of fortune they spotted an ad for a place which turned out to be fantastic.
The second is equipment. I was given a nice corner office, substantial financial support, a bike, a keyboard/mouse set, and a monitor, but not a computer. Admittedly, this is not a great loss, because setting up a new machine is almost as much hassle as bringing your own. This brings me to a point which has nothing to do with the institute, but which I’ll make here. What I would like are machines where you just need to push a button to have your exact workbench appear. This would be great even if it took a little installation time, as long as everything was automated, because you could just push that button ahead of time. Of course we do have Chromebooks, rollApp, Remote Desktop, et cetera, but none of this comes close to having your own settings. Indeed, today’s solution to the problem amounts to travelling with your own laptop — something which brings to my mind the expression “downfall of mankind.”
I am reminded of a Java project that I did during my undergraduate at La Sapienza. We had to program an application at home, and then show it to the professors in the department. My group was perhaps the only one which did not drag their own desktop computer to run the application. So much for Java. We were quite proud of showing up with just a floppy disk, until our application did in a few minutes something that had never done in days of intense domestic beta-testing.
Going back to the talks that we had, Zuckerman gave a talk about his impressive 2-source extractor with Eshan Chattopadhyay. One component of their construction is an extractor for n-bit sources where n-n0.99 bits are polylog(n)-wise independent, and the other n0.99 are an arbitrary function of the former, which answers a question raised in a paper of mine. Alexander Kulikov spoke about his better-than-3n lower bound for the circuit complexity of an explicit function, with Magnus Gausdal Find, Alexander Golovnev, and Edward Hirsch. Their strongest lower bounds are for computing extractors for degree-2 GF(2) polynomials, an object that is not currently available. And I talked about the Local Reductions developed with Jahanjou and Miles.
Thoughts 