Oded Wins The Knuth Prize

Just announced

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

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 congrads 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 add 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 congrads to Oded. Any thoughts of how the message to Ken and I was encoded?

TOC In The Future

Results of the panel at the Theory Fest

Géraud Sénizergues proved in 1997 that equivalence of deterministic pushdown automata (DPDAs) is decidable. Solving this decades-open problem won him the 2002 Gödel Prize.

Today Ken and I want to ponder how theory of computing (TOC) has changed over the years and where it is headed.

Of course we have some idea of how it has changed over the years, since we both have worked in TOC for decades, but the future is a bit more difficult to tell. Actually the future is also safer: people may feel left out and disagree about the past, but the future is yet to happen so who could be left out?

Does Logic Apply To Hearings?

The problem of mining text for implications

2016 RSA Conference bio, speech

Michael Rogers, the head of the National Security Agency, testified before the Senate Intelligence Committee the other day about President Donald Trump. He was jointed by other heads of other intelligence agencies who also testified. Their comments were, as one would expect, widely reported.

In real time, I heard Admiral Rogers’s comments. Then I heard and read the reports about them. I am at best puzzled about what happened.

Goldilocks Principle And P vs. NP

The rule of three

Wikimedia Commons source

Robert Southey was the Poet Laureate of Britain from 1813 until his death in 1843. He published, anonymously, “The Story of the Three Bears” in 1837.

Today Ken and I want to talk about the state of versus and the relationship to this story.

Stopped Watches and Data Analytics

Is this a new or old paradox?

UK Independent source—and “a gentle irony”

Roger Bannister is a British neurologist. He received the first Lifetime Achievement Award from the American Academy for Neurology in 2005. Besides his extensive research and many papers in neurology, his 25 years of revising and expanding the bellwether text Clinical Neurology culminated in being added as co-author. Oh by the way, he is that Bannister who was the first person timed under 4:00 in a mile race.

Today I cover another case of “Big Data Blues” that has surfaced in my chess work, using a race-timing analogy to make it general.

A Mother’s Day Cryptogram?

Or just human ingenuity at finding patterns in ‘random’ data?

Cropped from source

Bill Clinton was the 42nd President of the United States. He came close to becoming the first First Gentleman—or whatever we will call the husband of a female president. He is also a fan of crossword puzzles, and co-authored with Victor Fleming a puzzle for this past Friday’s New York Times.

Today we discuss an apparently unintended find in his puzzle. It has a Mother’s Day theme.

A Great Solution

A great conjecture too

Alternate photo by Quanta

Thomas Royen is a retired professor of statistics in Schwalbach am Taunus near Frankfurt, Germany. In July 2014 he had a one-minute insight about how to prove the famous Gaussian correlation inequality (GCI) conjecture. It took one day for him to draft a full proof of the conjecture. It has taken several years for the proof to be accepted and brought to full light.

Today Ken and I hail his achievement and discuss some of its history and context.