Shtetl-Optimized

From left: Amnon Ta-Shma, your humble blogger, David Zuckerman, Adi Akavia, Adam Klivans. Behind us: the majestic mountains of Banff, Canada, site of yet another complexity workshop, which I just returned from a couple days ago, after which I immediately had to move out of my apartment, which explains the delay in updating the blog. Thanks to Oded Regev for the photo.

A few highlights from the workshop:

• Rahul Santhanam presented a proof that for every fixed k, there exists a language in PromiseMA with no circuits of size n^k. This is a problem I spent some time on last year and failed to solve.
• Dmitry Gavinsky discussed the question of whether quantum one-way communication complexity can be exponentially smaller than randomized two-way communication complexity. Richard Cleve has a candidate problem that might yield such a separation.
• Ryan O’Donnell presented a proof that one can decide, using poly(1/ε) queries, whether a Boolean function is a threhold function or is ε-far from any threshold function. This is much harder than it sounds.
• I took a gondola to the top of Sulphur Mountain, where the above photo was taken. While walking amidst some slanty rocks, I slipped and twisted my ankle. I was hobbling around for several days afterward, but seem to be OK now.

Overwhelming everything else, alas, was a memorial session for Misha Alekhnovich. Misha, who loved extreme sports, went on a whitewater kayaking trip in Russia a month ago. At a dangerous bend in the river, his three companions apparently made it to shore safely, while Misha did not. He was 28, and was to get married a few days from now.

Misha and I overlapped as postdocs at IAS, and I wish I’d gotten to know him better then. From the conversations we did have, it was clear that Misha missed Russia and wanted to go back as soon as possible. The truth, though, is that I knew Misha less on a personal level than through his groundbreaking work, and particularly his beautiful paper with Razborov, where they show that the Resolution proof system is not automatizable unless FPT = W[P]. I still find it incredible that they were able to prove such a thing.

Lance has already discussed the memorial session, in which Eli Ben-Sasson and Sasha Razborov offered their personal remembrances, while Toni Pitassi and Russell Impagliazzo gave talks about Misha’s work, emphasizing how the P versus NP question always lay just beneath the surface. It occurred to me that an outsider might find these talks odd, or even off-putting. Here we were, at a memorial for a dead colleague, talking in detail about the definition of automatizability and the the performance of the DPLL algorithm on satisfiable CNF instances. Personally, I found it moving. At a funeral for a brilliant musician, would one discuss his “passion for music” in the abstract without playing any of his songs?

The tragic loss of Misha has reinforced a view I’ve long held: that if challenge is what you seek, then the thing to do is to tackle difficult open problems in math and computer science (or possibly physics). Unlike the skydiver, the kayaker, or the mountain-climber, the theorem-prover makes a permanent contribution in the best case, and is down a few months and a few hundred cups of coffee in the worst case. As for physical challenges, walking around heavily-populated tourist areas with slanty rocks has always presented more than enough of them for me.

This entry was posted on Sunday, September 3rd, 2006 at 7:01 pm and is filed under Adventures in Meatspace, Complexity. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.