Almost ten years have passed since Shimon Even died, and this is the fifth time we are handing this award that commemorates him. I think it is adequate to share some of Shimon's legacy with those who were not fortunate enough to have known him in person.
Since Shimon was a sworn non-conformist, it feels quite odd to talk of his legacy. Furthermore, formulating the principles that govern his behavior was not something that he would normally do. Still, I think that two principles stood out, and I will illustrate them by two anecdotes that boil down to things he said on the spot.
Shimon had his own style of presenting proofs, preferring a focus on the essential ideas over a formal derivation of a QED line. This style was not popular with students who just wanted to have an organized summary and did not care of real understanding. So, once when he completed a proof at his undergraduate class on Graph Algorithms, a student asked (with some annoyance): Is this a proof? What is a proof? Shimon answered on the spot: A proof is whatever convinces me.
My guess is that the student who challenged Shimon took this answer as arrogant and/or as authoritative, but I took it as a profound intuition about what proofs actually are. I think it is remarkable that Shimon did not feel that he needs to answer with an attempt for a pseudo-formal definition. Nor did he view the question as philosophical and abstract. To him the question and the answer were simple and concrete: Proofs are instruments for down-to-earth goals like distinguishing truth from false and understanding the truth. Actually, for him, being convinced was linked to understanding; he would not be truly convinced of a fact until he understood why it is true.
Another aspect worthy of mention is that Shimon's answer hints that being convinced (and understanding in general) is a subjective thing. Although we do strive for the objective, at the last account we cannot really claim it. We do seek proofs that convince all and are understandable by all, but at the last account we can only judge their convincing and/or explanatory power with respect to ourselves.
Half a decade later, I was reminded of this incidence when thinking about the notion of interactive proof systems. I felt that Shimon's answer a proof is whatever convinces me is a perfect answer to the question in what sense these (and other probabilistic proofs systems) are ``proofs''. The answer is that they convince the (automatic) verifier. (Interestingly, zero-knowledge proofs break the link between being convinced and understanding; hence, they are proofs only with respect to verifiers that settle for verifying the truth rather than understand it.)
Once, somebody told Shimon of a problem, which Simon liked. When the presenter wanted to motivate the problem by some concrete applications, Shimon stopped him saying When I see a natural problem I don't care about applications.
I think this reflects Shimon's choice of research problems. He worked on problems that he found interesting, and he typically found problems interesting when they touched on central issues (i.e., issues that are central to the understanding of an area). Such a relation made these problems natural to him, and the fact that there are applications to natural problems was secondary as well as a tautology that need not be verified.
Again, the curse of subjectivity arises: What is interesting or natural depends on one's understanding of the field. Although we do strive for the objective, at the last account we cannot really claim it. Note that he said ``when I see a natural problem'' meaning ``when I recognize it as natural'' (based on my understanding of the field). Still, our aim is a common understanding of the field.
For additional stories about Shimon Even see HERE.
Back to Oded Goldreich's homepage.