Oded Wins the Knuth Prize | Hacker News Reader

Oded Wins the Knuth Prize

rjlipton.wordpress.com

129 pointssndean29 comments

The post mentions him apologizing "For not declining the award—as some might have hoped" - can anyone comment on why that might have been the case?

Just a guess: It's a joke, referring to the fact that most people who win the $2.56 checks from Knuth don't cash them in.

Knuth's checks have their own wikipedia page: https://en.wikipedia.org/wiki/Knuth_reward_check

From the Wiki page:

> Very few of these checks were actually cashed, even the largest ones. More often they have been framed and kept as "bragging rights".[4][5]

Cashing a check only removes it from your possession if you hand it in to do so. Banks these days need only a physical scan of a check, e.g. via mobile phone deposit. Why not do both? There's nothing wrong with taking payment for your efforts.

AFAIK, after deposit, you're supposed to void a check by either destroying it or writing something on the front of it (such as "void")

(void*)

http://www-cs-faculty.stanford.edu/~knuth/boss.html

The Knuth prize is different from the reward given for finding a bug in TeX.

He's famously opinionated: http://www.wisdom.weizmann.ac.il/~oded/on-awards.html

Oded has argued previously[1] against awards in academia.

[1]: http://www.wisdom.weizmann.ac.il/~oded/on-awards.html

People may be tempted to call this hypocracy; i think it's classy.

Why? He argues that other people shouldn't get awards, but he's willing to take them himself? Honestly, I don't get it. His stance does real harm to young theorists, especially those doing cross-disciplinary research.

But I think this is a minor issue, and don't want to take away from the bigger point, which is the award that he very much deserves.

I think there is a difference between arguing "there shouldn't be as many awards" and being negative about people receiving them. Has he demanded/argued for other people to decline their awards before?

Disliking a system and even publicly arguing against it, while still participating in it, is not hypocrisy, it is pragmatism.

It would be hypocrisy if he started giving out his own award.

Some would even argue that you can't meaningfully criticise a system without experience in it.

Some context: doubly efficient interactive proofs are one of the fundamental ideas that make Zcash possible on modern hardware.

No, doubly efficient IPs do not have much to do with ZCash. deIPs are currently too weak to prove the general NP statements that ZCash requires.

ZCash relies on a different kind of "proof" system: SNARKs.

There's many differences between the two:

a) deIPs assume a computationally unbounded adversary, whereas SNARKs assume a polytime adversary.

b) deIP constructions currently suffice only for a limited class of languages, whereas SNARKs can prove any NP statement.

c) SNARKs have zero knowledge variants, whereas it is not clear how to extend many deIP constructions to be zero knowledge without changing the model (ala https://eprint.iacr.org/2017/305).

d) Most deIPs are interactive proof systems, whereas SNARKs are non-interactive.

Huh, you're correct. My professor said doubly-efficient IPs were used in Zcash, maybe he just meant as inspiration?

I think what you are claiming here is misleading.

Some pre-processing SNARK constructions (particularly ones used by some ZCash scientists) are based on multi-round interactive proof systems which reduce to one round (depending on how you count) when you relax some requirements. Such relaxations include weakening the adversary from being computationally unbounded to polynomial time bounded, forcing the prover and verifier to use a specific set of functions, or restricting what kinds of statements can be proven. Oded's work on efficient interactive proofs contributed to this effort. It is partially this efficiency that helps SNARKs actually be "succinct" and quick to verify.

You should check out some of the citations to Oded's work in https://eprint.iacr.org/2012/718.pdf (which is co-authored by Alessandro Chiesa of ZCash) and see for yourself.

One can construct SNARKs from succinct MIPs, but these are again very different from deIPs. Sure, both SNARKs and deIPs involve highly efficient verifiers, and there is some overlap between the techniques used for succinct MIPs and deIPs, but that's pretty much where the similarities end. Furthermore, MIP based SNARKs are way too inefficient, and definitely not the ones used in Zerocash.

There are no constructions of SNARKs from deIPs, nor vice versa. In particular, one cannot construct laconic IPs at all for NP like languages.

P.S.: I'm Alessandro's student ;-)

Took me a while to register that the simple letter replacement cipher used on that message has 26! = 403291461126605635584000000 possible keys... Ha!

Oh that's clever. By noting the zeroes I just assumed the joke was that the number was embarrassingly factorable.

"ODED WINS THE KNUTH PRIZE"

I had a little help from context ;)

For those who don't get it, the cryptogram "YXWX APRN LKW CRTLK DHPFW" decodes to the above.

I was still deciding between "ODED GIRL SHE BRUSH TWICE" and "ODED MANY THE KNUTH SLAVE". This makes more sense.

Looks like he does research in theoretical computer science, applied to cryptography. With his academic expertise, what kind of industry jobs would fit his skill sets? He wouldn't fit the typical tech security job.

> With his academic expertise, what kind of industry jobs would fit his skill sets?

I would imagine his pick among the various industry research labs, if he wanted them.

> He wouldn't fit the typical tech security job.

Nor would he be a good fit as a line cook or as a surgeon...

I'm not sure if you're trolling or not, but Oded Goldreich is one of the founding fathers of cryptography...

He could get a job pretty much anywhere he wanted to, doing whatever he wanted.

From his FAQ: "About My Areas of Non-Expertise (e.g., Applied Cryptography)

I believe that sound practice of Cryptography has to be based on firm theoretical foundations. Still, this necessary condition is not sufficient, and expertise in applied (or practical) aspects of cryptography requires more than understanding of the theoretical foundations of Cryptography. For example, although I consider myself an expert on the theoretical foundations of Cryptography, I have very little knowledge of the applied (or practical) aspects of cryptography. In particular, please do not ask me to evaluate the security of any specific construct.

About Consulting

My above statement of limited knowledge of the applied (or practical) aspects of cryptography means that I'm not the right person to ask for consulting regarding the latter aspect. On top of this, I am not interested at all in consulting to or being involved in any commercial enterprise. My main reason is my unwillingness to make any commitment to spend time on anything other than my research and personal interests. Unfortunately, for lack of time, I properly pursue only a tiny part of my research and personal interests, and I have no intentions of making this part even smaller."

Reply on news.ycombinator.com