# Wei_Dai comments on Correlated decision making: a complete theory - Less Wrong

7 26 September 2009 11:47AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: 27 September 2009 12:40:06PM 2 points [-]

I think it's because we're mainly focused on getting ideas right - most of the time, writing out the equation is merely a confirmation of what we allready know to be true. So often, a mathmo will write out a series of equations where the beginning will be true, the middle completely wrong, and the conclusion correct.

I wonder why that doesn't work in cryptography. There are several well-known examples of "security proofs" (proof of security of a crypto scheme under the assumption that some computational problem is hard) by respected researchers that turn out many years after publication to contain errors that render the conclusions invalid.

Or does this happen just as often in mathematics, except that mathematicians don't care so much because their errors don't usually have much real-world impact?

Comment author: 27 September 2009 07:08:09PM 1 point [-]

Or does this happen just as often in mathematics, except that mathematicians don't care so much because their errors don't usually have much real-world impact?

The strongest theorems are those that have multiple proofs, or where the idea of the proof is easy to grasp (think Godel's incompleteness theorem). Proofs that depend on every detail of a long tedious calculation, and only on that, are rare.

Proof that err by using implicit lemmas, or assuming results they can't assume, are much more common, and mathematicians know this and are much more on guard for those errors.

Comment author: 29 September 2009 12:04:20AM 0 points [-]

The strongest theorems are those that have multiple proofs, or where the idea of the proof is easy to grasp (think Godel's incompleteness theorem). Proofs that depend on every detail of a long tedious calculation, and only on that, are rare.

But those kinds of proofs are not rare in cryptography. Which suggests that there's a selection effect going on in mathematics, where mathematicians choose which problems to work on partly by how likely the solutions to those problems will involve "strong" theorems with multiple proofs and perhaps be easily accessed by their intuitions.

Now what happens when the problem picks you, instead of you picking the problem? That is the situation we're in, I think, so sloppiness is a worse problem than you might expect.

Comment author: 29 September 2009 02:34:35AM 1 point [-]

This reads to me like macho bragging.

Both math and crypto contain errors. Are they the result of sloppiness? the kind of sloppiness Stuart Armstrong attributes to mathematicians?

I don't know much about crypto. LF is said to be repeatedly wrong (in crypto? in another field?). That must constitute a kind of sloppiness. Is it correlated with other kinds of sloppiness?

i see two kinds of sloppiness I see attributed in this thread to mathematicians: (1) that detectable by copyediting; (2) focusing on the hard parts and trusting the easy parts to take care of themselves. (2) can lead to (1). There's a third kind of sloppiness common in senior mathematicians: they supply the proof, but refuse to give the statement. Much of the difference is probably material that mathematicians include that people in CS simply omit. (is crypto published in conferences?)

Comment author: 29 September 2009 03:00:34AM 0 points [-]

Both math and crypto contain errors. Are they the result of sloppiness? the kind of sloppiness Stuart Armstrong attributes to mathematicians?

According to Stuart, in math there are often errors where "beginning will be true, the middle completely wrong, and the conclusion correct". I was saying that this kind of error doesn't seem to occur often in crypto, and trying to figure out why, with no bragging intended. Do you have another hypothesis, besides the one I gave?

LF is said to be repeatedly wrong (in crypto? in another field?).

What is LF?

Comment author: 29 September 2009 03:15:25AM 0 points [-]

My working hypothesis is that math and crypto are very similar, this kind of error occurs frequently, and you just don't notice. What little crypto I know could be called complexity theory. I've read very little and heard it mainly orally. I've experienced this kind of error, certainly in oral complexity theory and I think in oral crypto. Of course, there's a difference when people are trying to reconstruct proofs that are stamped by authority.

I thought it possible you were talking about the person LF.

Comment author: 27 September 2009 06:14:01PM 1 point [-]

Yes, mathematicians produce errors that stand for decades, but they aren't errors that are detectable to copy-editing. Surely the errors you mention in crypto weren't caused by substituting pz for px! How could it have stood so long with such an error? Also, such a random error is unlikely to help the proof. If you are approximating something and you want different sources of error to cancel, then a minus sign could make all the difference in the world, but people know that this is the key in the proof and pay more attention. Also, if flipping a sign makes it true, it's probably false, not just false, but false with a big enough error that you can check it in small examples.

"Beware of bugs in the above code; I have only proved it correct, not tried it.'' - Knuth

Comment author: 27 September 2009 02:07:35PM 1 point [-]

I've heard stories (from my math professors in college) of grad students who spent multiple years writing about certain entities, which have all sorts of very interesting properties. However, they were having difficulties actually constructing one. Eventually it was demonstrated that there aren't any, and they had been proving the interesting things one could do if one had an element of the empty set.

http://en.wikipedia.org/wiki/Principle_of_explosion

Mathematicians do make errors. Sometimes they brush them aside as trivial (like Girard in Nesov's example), but sometimes they care a lot.