Skip to content

Oded Wins The Knuth Prize

June 22, 2017


Just announced {\dots}

Oded Goldreich is one of the top researchers in cryptography, randomness, and complexity theory.

Today Ken and I wish to thank the Knuth Prize Committee for selecting Oded as the winner of the 2017 Knuth Prize.

It is no doubt a wonderful choice, a choice that rewards many great results, and a choice that is terrific. Congrads to Oded. This year the choice was only announced to the general public at the last minute. Ken and I at GLL got an encrypted message that allowed us to figure it out ahead of time. The message was: YXWX APRN LKW CRTLK DHPFW The encryption method is based a code with over

\displaystyle 403291461126605635584000000

keys, and so was almost unbreakable. But we did it.

His Talk

Oded gave his talk last night to a filled ballroom: one of the perks of winning the Knuth Prize. I had sent him congrats as soon as I heard he had won and added I looked forward to his talk. He answered essentially “thanks for increasing the pressure on me.” I know he was kidding since he always gives great talks.

I just heard the talk; and he delivered, with his usual mixture of fun and seriousness. The talk had two parts. The first started with some apologizes.

  • For lying to people who asked me if I was attending STOC 2017.

  • For not declining the award—as some might have hoped.
  • For not being a good speaker: unclear pronunciation, undisciplined, moody, Powerpoint-challenged—uses too dense slides.

He added some wonderful comments like: “I had some jokes but I forgot them.” This brought a huge laugh down—we theory people just love diagonal arguments.

This part continued with some interesting comments on the nature of Theory. Some of it was advice to junior members and some advice to senior members. My favorite were:

  • Do not confuse what is obvious a posteriori with what may be obvious a priori.

  • Do not complain that proofs are elementary, and have no new ideas.

I like these suggestions very much. I have more than once been on the receiving end of “but it is so simple.” I would like to think that I rarely have said that to someone else.

Oded then moved on to the technical part of his talk. I personally liked the first part very much and would have loved to hear more of his comments of this nature.

But Oded wanted to use this talk to also highlight some very interesting new results on proof systems. Here he spoke about On Doubly-Efficient Interactive Proof Systems. He introduced the idea by using the movie When Night is Falling. It is a Canadian Film from 1995 involving Petra and Camille. My wife, Kathryn Farley, who was sitting next to during the talk, immediately whispered to me: “what a wonderful movie” as soon as Oded put a picture of Petra and Camille on the screen. We all have our own expertise.

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear-time. See here for a paper on the subject joint with Guy Rothblum. I think we will report on this material in more detail in the future, but here is part of their abstract:

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear-time. We present direct constructions of doubly-efficient interactive proof systems for problems in P that are believed to have relatively high complexity. Specifically, such constructions are presented for t-CLIQUE and t-SUM. In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).

Open Problems

Again congrats to Oded. Any thoughts of how the message to Ken and me was encoded?

[some word fixes]

Advertisements
13 Comments leave one →
  1. June 22, 2017 1:49 pm

    Substitute YXWX = Oded

    • June 25, 2017 4:18 pm

      Sometimes the most considered editor actions are non-actions. When Dick used “YXWX” for “Oded” in his early draft (before Oded’s talk), I thought about the closeness to “YHWH” as something to consider avoiding—but note a precedent: Knuth himself referred to John Conway as “J.H.W.H. Conway” in his fable of Conway’s creation. In the end, since it was after all X not H, I silently let it stand. I then went off-Net basically until today in Krakow.

  2. June 22, 2017 2:57 pm

    May not be how it was decoded, but one can try guessing it may be a substitution cipher with spaces mapped to spaces:
    YXWX APRN LKW CRTLK DHPFW
    ???? WINS THE KNUTH PRIZE
    and just guess some words from context 🙂 Now noticing that this guess fits (the P→I, R→N, L→T, K→H, W→E transformations all occur twice), lets us infer the first word to be
    ??E? with the second and fourth letters the same, and at this point I imagine there are very few Knuth-Prize-eligible candidates with such a name. 🙂

  3. Jeff Fields permalink
    June 22, 2017 3:17 pm

    YXWX APRN LKW CRTLK DHPFW looks like just a simple substitution cipher, right? For ODED WINS THE KNUTH PRIZE.

  4. June 22, 2017 3:25 pm

    The encoded message is “ODED WINS THE KNUTH PRICE”.
    It’s a classic monoalphabetic substitution cypher, with the following substitutions:

    W->E
    K->H
    L->T
    P->I
    R->N
    X->D
    A->W
    C->K
    D->P
    F->C
    H->R
    N->S
    T->U
    Y->O

    It’s very easy to recognise because the encoded message keeps the original frequencies and the trigraph “LKW”->”THE” is very helpful to start decoding the message.

    Mazzal tov Oded!

  5. June 22, 2017 3:26 pm

    YXWX APRN LKW CRTLK DHPFW = ODED WINS THE KNUTH PRIZE (simple replacement cipher)

  6. Mehdi permalink
    June 22, 2017 3:34 pm

    Interesting article, thanks.

    On the code used :
    YXWX APRN LKW CRTLK DHPFW
    Most certainly if you ask us it is not that tough.
    Indeed, YXWY -> ODED
    APRN -> WINS
    LKW -> THE
    CRTLK -> KNUTH
    DHPFW-> PRIZE

    At least similar letters match : Y O, W E, X D etc
    Best,
    Mehdi

  7. June 24, 2017 8:48 am

    Off topic:

    Hello,

    I would like to share something that you all would find it useful.

    I have created a power point slide that details the algorithm that I developed to find whether a given graph has clique of given size; maximum clique size of given graph.

    The algorithm is constructive, usable, complete exhaustive search. Time complexity is better than quasi-polynomial time where n is up to few 1000(s) and slower than quasi-polynomial time when n is above few 1000(s). Space complexity is O(n^3).

    Slides can be found at Slides(pdf) and Slides(tex)

    Working implementation of algorithm in C++ can be found at github

    Thanks for providing an opportunity to share this information.

  8. spencer permalink
    June 28, 2017 6:35 am

    403291461126605635584000000 = 26!. It looks like a lot written out, but it’s actually only 89 bits, many of which get leaked via the guessed plaintext.

    • Aula permalink
      July 1, 2017 10:17 am

      Since this message use only 14 of the 26 letters, the actual keyspace is much smaller.

  9. AdC permalink
    July 6, 2017 10:26 am

    Prize 5000,00 dolares shows how important he is

Trackbacks

  1. Oded Wins The Knuth Prize | ExtendTree
  2. TheoryFest + wutorial updates | Windows On Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s