Silvio and Shafi win Turing Award

Today I break long radio silence to deliver some phenomenal news.  Two of the people who I eat lunch with every week—my MIT CSAIL colleagues Silvio Micali and Shafi Goldwasser—have won a well-deserved Turing Award, for their fundamental contributions to cryptography from the 1980s till today.  (I see that Lance just now beat me to a blog post about this.  Dammit, Lance!)

I won’t have to tell many readers of this blog that the names Goldwasser and Micali—or more often, the initials “G” and “M”—are as ubiquitous as Alice and Bob in modern cryptography, from the GGM construction of pseudorandom functions (discussed before on this blog), to the classic GMR paper that introduced the world to interactive proofs.  Besides that, Shafi and Silvio are known as two of the more opinionated and colorful characters of theoretical computer science—and as I learned last week, Silvio is also an awesome party host, who has perfect taste in sushi (as well as furniture and many other things).

I wish I could go on right now talking about Shafi and Silvio—and even more, that I could join the celebration that will happen at MIT this afternoon.  But I’m about to board a flight to LAX, to attend the 60th birthday symposium of longtime friend, extraordinary physicist, and sometime Shtetl-Optimized commenter John Preskill.  (I’ll also be bringing you coverage of that symposium, including slides from my talk there on hidden variables.)  So, leave your congratulations, etc. in the comments section, and I’ll see them when I land!

11 Responses to “Silvio and Shafi win Turing Award”

  1. Guy Rothblum Says:

    Congratulations Shafi and Silvio!!! By now their work has inspired generations of researchers in cryptography, complexity, and theoretical CS.

    And, since I see that we’re counting, I cannot resisit also congratulating Omer for the FIRST blog post announcing this wonderful news 🙂

  2. Gil Kalai Says:

    Congratulations to Shafi and Silvio for revolutionizing cryptography, many wonderful results, and the richly deserved Turing award!

    And congratulations to John. Happy birthday-conference!

    (It is pleasing to know in person all these great guys.)

  3. Scott Says:

    Guy: Thanks for the link to Omer’s blog! I also found a good press release from Weizmann Institute here. (Turns out I have in-flight Internet…)

  4. Ungrateful_Person Says:

    Really wow! Congratulations to Silvio and Shafi

  5. Peter Norvig Says:

    Congrats! This is the first time that a Turing winner was someone I sat next to in class; a great and well-deserved accomplishment for Shafi and Silvio, but maybe a sign I’m getting old …

  6. S Says:

    Aside from congratulations to them, I just had a question about the announcement here itself 🙂 I thought alphabetical ordering is the standard in the theory community? Both title and first sentence in the blog post are switching the order (and it doesn’t matter how you sort, by first or last name).

  7. Scott Says:

    S #6: I decided to mix it up a little.

  8. Ashley Lopez Says:

    Hi Scott,

    I was going through your slides from Prof. Preskill’s birthday symposium.

    It would take me some work to read them reasonably well, but I already have a question – why is the “product dynamics” picture not seen among the usual quantum interpretations? Of course, it is a most crazy thing, but is THAT a problem?

    (That ‘picture’ would not hold true if you take into account special relativity, am I right? You have a pair of bits in (|00> + |11>)/(square root of 2), non-relativistically they could be just two bits assuming ‘0’ and ‘1’ randomly at each instant, only both always in the same (classical) state. But relativistically there are no ‘same instants’ if they are not on top of each other. Is THAT the problem?)

  9. Scott Says:

    Ashley Lopez #8: It’s hard to think of anything “wrong” with the product dynamics, apart from the fact that it predicts that everything around us just flit into existence a moment ago and will flit out of existence again a moment later! (In a similar sense, it’s hard to think of anything “wrong” with solipsism, or the idea that I’m a brain in a vat, etc.)

    In particular, the product dynamics satisfies the “commutativity” axiom, and is therefore almost unique among discrete dynamical theories in not creating any obvious problem for special relativity. See my paper for more.

    As for why it’s “not seen among the usual quantum interpretations,” I don’t know but can guess. I remember a passage in Bell’s “Speakable and Unspeakable” book where he discussed a similar proposal, comparing it to the creationist belief that the universe was created in 4004 BC with the fossils already in the ground, light from distant stars already headed toward us, etc. If you accept that sort of radical skepticism about the past, then it seems impossible to do science.

    For example, suppose you shoot a photon at a half-silvered mirror; then you ought to be able to use the Born rule to calculate the probability that you’ll see the photon fly off in one direction vs. the probability that you’ll see it fly off in the perpendicular direction. According to the product dynamics, however, it’s overwhelmingly more likely that you, the photon, the mirror, and all your records of the experiment will disappear in the next instant, to be replaced by something totally different (but consistent with its own illusory “past” that never actually happened). So you might argue that every time that doesn’t happen, we obtain overwhelming experimental evidence that the product dynamics can’t be right. (Though of course, if it did happen, then by assumption we wouldn’t remember it! 🙂 )

  10. John Sidles Says:

    A précis of Alexei Kitaev’s talk “Berry curvature for many-body systems” ( arXiv:1302.4122 ? ) would be very welcome … post-Hilbert dynamical theories generically associate anomalous Berry-type phases to high-order quantum correlations.

  11. Scott Says:

    John Sidles #10: Sorry, I’m flying back this morning and will have to miss that one—maybe someone else can give a report!