Skip to content

How To Carry Fame

March 10, 2014


Long proofs are not always the most important results

Unknown

Michael Rabin is visiting Georgia Tech today and tomorrow to give a pair of distinguished lectures. Both of these will be on applications of cryptography. One is to help auctions avoid cheaters, while the other is to help elections avoid cheaters. I see a pattern. Ken sees another pattern— he is helping chess tournaments avoid cheaters.

Today I want to comment about Rabin’s fame and what makes a result important.

I have known Michael since I was a graduate student at CMU—I have talked about this before here. In the decades since then I have heard him given many talks, all of which have been brilliant. He is one of the best presenters of technical material I have every seen, perhaps the best in the world. My “proof” of this statement is:

that I can still recall—in detail—most of his talks, even ones from decades ago.

Can you recall that talk you heard last year, or even one you heard last month? I have trouble recalling my own talks. But Michael’s talks are special, memorable, informative, clear, and fun.

Great Talks

I have selected a few talks of Michael that I recall in great detail—they span about forty years. There are many others that I could have added, but these should make my point.

{\bullet } His talk on Theoretical impediments to artificial intelligence, was the first of his talks that I had ever heard. It was at the 1974 IFIP Congress, which occurred in Stockholm Sweden. There was a time when the IFIP Congress was a major conference that many of us went to. I met Dick Karp there for the first time.

{\bullet } His talk on the introduction of randomness to algorithms, which was given at Yale when I was there as a junior faculty member. It was in 1977, I recall. This talk made the case for the power of randomness—Michael showed that randomness could help in a certain geometric search problem. I talked about this in detail in the same post with the CMU story.

{\bullet } His talk on the Karp-Rabin pattern matching algorithm was given in the 1980’s at Princeton University. We have also talked about this before here.

{\bullet } His talk on hyper-encryption was given at Georgia Tech about ten years ago. This was an cool idea—I believe—on using non-complexity assumptions to build encryption methods that were very powerful. The short insight was that memory is expensive, and one could defeat an adversary that had limited memory. This yielded a protocol that needed no assumptions about factoring or the existence of one-way functions.

Great Results

Why indeed is Rabin famous? He received the Turing Award with Dana Scott for their work on finite state automata (FSA). I would argue that his most exciting results were curiously his least deep results. We all know about FSA; his introduction of randomness to all parts of computing; his primality test, independent but related to Gary Miller’s work; his pattern matching algorithm with Karp; and much more. Yet, I would argue that his deepest result is probably his least known. It was, is, his brilliant work on S2S.

Second Order Monadic Theory

What is S2S?

There are many logical theories that we study, such as Peano Arithmetic (PA). PA is a first-order theory. This means that quantifiers can only range over individual elements—in PA they range over integers. Thus, in PA we can say

\displaystyle  \forall x \ \exists r \ \exists s \ \exists t (t\neq 0 \wedge tx = r^{3} + s^{3}).

This states that all numbers have a non-zero multiple that is a sum of two cubes. This is true—but it is not trivial.

The reason PA is so powerful is that it allows both addition and multiplication. Given a statement like the above about cubes it is impossible, in general, to decide whether the statement is true or not.

We obviously like decidable theories since at least in principle they allow us to tell if a statement is true or false. Of course if {\mathsf{P} \neq \mathsf{NP}}, then even for a decidable theory it may be hard to tell whether something is true. But still decidable is a great property for a theory to have.

A difficulty is the tension between being an expressive theory and being decidable. PA is very expressive, most everyday theorems of mathematics can be proved in it, at least in principle. It is so expressive that even weak subtheories are undecidable.

Enter S2S. The theory S2S is a different kind of theory from PA. While PA is a first-order theory, S2S is a second-order theory. The “S” in “S2S” stands for second order. It allows quantifiers to range over individual elements and also over finite or infinite sets of elements. The basic objects in S2S are finite paths in the infinite binary tree.

RabinTree

In S2S we can talk about the left and right successor to any such element: if {x} is an element, then {x0} and {x1} are the respective successors. Since it is a second order theory we are also allowed quantifiy over sets of such elements.

Decidedly More Power

The ability to quantify over sets makes S2S very powerful and expressive. For example, here are two notions expressed formally:

lex

finite

The magic of this is that while the theory is expressive, it is not too expressive. Indeed the Rabin proved in 1969:

Theorem 1 The monadic second order theory of the infinite binary tree is decidable.

When I first looked at Rabin’s paper, as a graduate student at CMU, it was not the depth of his proof, which is wonderful, but rather the array of applications that followed that excited me. One measure of the depth of a theorem is the number of open problems it solves. Rabin’s theorem can be used to prove the following other theories are decidable:

  • The first order theory of rationals with the order {<} relation.
  • The first order theory of boolean algebras with ideals.
  • Certain modal logics, such as S4.

These results follow by encoding the decidability question into the powerful theory S2S and invoking Rabin’s Theorem. See this for a nice summary of S2S in slide format by Shane Steinert-Threlkeld.

The proof of Rabin’s Theorem was a tour-de-force. It requires clever definitions and some quite detailed inductive arguments. Since his original proof people have found “easier” proofs, but the original was quite deep and intricate.

I would argue that this theorem is one of the deepest results of Rabin’s many beautiful results over his long career. It is well known to those who work in logic and automata theory, but is perhaps less known to the whole theory community. If you already knew it fine, if not, then I hope you begin to appreciate the depth of his work.

Open Problems

Perhaps a lesson here for all: fame comes from results that are game-changers, which does not always mean they are deep long complex arguments. Sometimes that is the case: clearly the solution to Fermat Last Theorem and the Poincaré Conjecture are famous and deep results. Yet many times I think Rabin’s situation is more often the case: a simple to state result that yields an “ah” moment, that opens doors for others, that changes the landscape of thinking about an area, is the most important type of result. Rabin has many many of these results. I would argue that without S2S he still would be one of the greatest theorists who has ever lived.

What do you think?

About these ads
15 Comments leave one →
  1. March 10, 2014 10:52 am

    In presenting technical materials my candidate is Ron Graham.

    Since the title is “How to Carry Fame” I would like say that sometimes you don’t want to carry fame or a like. Very recently in another blog (http://jeremykun.com/2014/02/21/on-coloring-resilient-graphs/ ) I have made a comment(s) on planar graph coloring problem that leads to an (dangerous) conclusion such that P=NP. Certainly this is not what I am looking for but if you have a theorem:
    “A planar graph is 3-colorable if and only if there exists no crash of two induce almost uniquely 3-colorable subgraphs.” and an efficient coloring algorithm (spiral chain coloring) then be ready for the fame or not.

  2. March 10, 2014 12:20 pm

    I think you are quite sure you have the proof that S2S is decidable iff it is undecidable. This is a property that many people know but it is so harsh on them. Obviously, Rabin is a great theorists as you said, maybe even more despite the fact that there is no theory at all.

    Best,

    Rafee Kamouna.

  3. March 11, 2014 1:58 am

    I am sorry to inform that my “comments” have been removed from the blog since “On Coloring Resilient Graphs” is not a place to discuss P vs NP.

  4. March 11, 2014 4:34 am

    Dear Ibrahim Cahit,

    Spread a rumor that your P vs. NP proposal is a Deolalikar-endorsed one. Only then, billions of researchers have to study, analyze, peer-review your work online, on the fly and on the spot. Don’t ask me for the reasons Why?

    best,

    Rafee Kamouna.

    • March 11, 2014 12:20 pm

      Dear Rafee,

      Thanks for the advice. I think Cook (accidentally) did the same thing for Deolalikar (?)

      best

      Cahit

      • March 11, 2014 5:42 pm

        So, did you prove P=NP or P!=NP? Have you submitted it for peer-review? What was the feedback?

        best,

        Rafee Kamouna.

      • March 11, 2014 6:52 pm

        It is early to announce formally the proof that P=NP. Let me list the steps that may lead to this surprised result.
        1. As I indicated in my first comment above I have a theorem which gives a simple necessary and sufficient condition for the three colorability of a planar graph. That is a planar graph has an chromatic number 3 only if it is crash-free. (see definition of the crash e.g. c-crash, c-match and c-trap (single vertex c-crash) in my incomplete paper [1].
        2. Second step of the proof is an algorithm (spiral chain coloring(SCC) which has been used in the non-computer proof of the four color theorem in 2004. SCC algorithm not only colors the vertices of a planar graph but also detects crashes if there are any. Another words SCC colors the vertices with respect to the chromatic number of the planar graph. Time complexity of the coloring algorithm would not greater than kO(n), k>1.

        I have not submitted my result in the form of a paper for peer-review. Planning to present at the ICM 2014 Seoul which I think would be a good place for the feedback.

        [1] .https://www.academia.edu/3698249/Almost_Uniquely_Chromatic_4-Critical_Planar_Graphs#1

        for the illustrations of SCC algorithm

        [2] http://www.flickr.com/photos/49058045@N00/5410703782/ (dedecting c-crash by SCC)

        [3] http://www.flickr.com/photos/49058045@N00/188725295/ (dedecting c-trap (single vertex c-crash))

        [4]https://www.academia.edu/440527/VISUALIZATION_OF_THE_FOUR_COLOR_THEOREM (particularly see Fig. 2 for the selfishness of using fourth in the spiral chain coloring algorithm for the maximal planar graph.)

  5. March 11, 2014 5:59 am

    Theorem: P=NP P!=NP.

    Proof: The Kleene-Rosser paradox is a counter-example to NP-completeness.

    ================================================

    Step 1. Cook_Levin: For all w in L in NP,
    M accepts w \exists A(w)=SAT.

    Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
    M_KR accepts w_KR e^-1(w_KR)= NOT e^-1(w_KR).

    Step 3. Put M=M_KR and w=w_KR.

    ==> L.H.S. of (1) = L.H.S. of (2).

    ==> R.H.S. of (1) = R.H.S. of (2).

    ==> There is no SAT(w_KR).

    ==> L_KR={w_KR_i} is in NP and NOT NP-complete.

    ==> L_KR is a counter-example for NP-completeness.

    ==> SAT is (NOT) NP-complete.

    ==> SAT is NP-complete SAT is (NOT) NP-complete,
    Cook’s proof is still correct despite the contradiction.

    ==> P=NP P!=NP.
    ================================================

    best,

    Rafee Kamouna.

  6. March 11, 2014 6:15 am

    P=NP P!=NP.

  7. March 11, 2014 8:21 pm

    In the above proof sketch, correcting typos that wordpress causes with Math symbols.

    =================================================================

    Theorem: P=NP iff P!=NP.

    The Kleene-Rosser paradox is a counter-example to NP-completeness.
    ======================================

    Russell’s Paradox: The set that contains all the sets that do not contain themselves. If you ask the question:”Does it contain itself?”. The answer would be it contains itself iff it does not contain itself.

    The Kleene-Rosser Paradox: Roughly, the function that may not be applied to itself, when combined with itself, it negates itself.

    This function is a lambda expression as “k:= NOT (x x)” which reads: The meaning of k is: “x” may not be applied to “x”. Then deriving “kk” results in the paradox:

    kk= NOT kk

    If you assume that this function is total, you derive a contradiction, then it is not total. Then, if you assume that it is not total, again, a contradiction is derived, then it is total. So, it is total iff it is not total. The Church-Rosser argument shows that this function is undefined. Here,

    http://kamouna.wordpress.com/2013/08/16/all-mathematical-systems-are-inconsistent/

    it has been shown as defined iff it is undefined and decidable iff it is undecidable, both on the lambda-calculus and Turing machines. Below is a proof sketch.

    ======================================
    Proof:

    Step 1. Cook_Levin: For all w in L in NP,
    M accepts w iff \exists A(w)=SAT.

    Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
    M_KR accepts w_KR iff e^-1(w_KR)= NOT e^-1(w_KR).

    Step 3. Put M=M_KR and w=w_KR.
    ==> L.H.S. of (1) = L.H.S. of (2).
    ==> R.H.S. of (1) = R.H.S. of (2).
    ==> There is no SAT(w_KR).
    ==> L_KR={w_KR_i} is in NP and NOT NP-complete.
    ==> L_KR is a counter-example for NP-completeness.
    ==> SAT is (NOT) NP-complete.
    ==> SAT is NP-complete SAT is (NOT) NP-complete,
    Cook’s proof is still correct despite the contradiction.
    ==> P=NP iff P!=NP.
    ======================================

    best,

    Rafee Kamouna.

  8. March 12, 2014 6:58 am

    So, was your work accepted by ICM and your presentation is confirmed.

    best,

    Rafee Kamouna.

  9. March 12, 2014 2:00 pm

    Dear Dick and Ken, I also have memories spanned over many decades of Michael’s lectures. I was too young to hear in real time Rabin’s decidability result. What I remember being told about it is that many people expected the opposite result! But I did remember as a student two lectures on randomness: one presenting the paradigm of randomaized algorithm, and a mathematics colloquium lecture about Rabin’s efficient primality testing which also was described in real time a new mathematical paradigm: proving a mathematical statements with high probability. I remember also vividly Rabin’s description of ultraproduct from a model theory course in the 70s. A lecture on an algebraic algorithm for matching, And a byzantine general lectures from the 80s and many more… Also the application of zero knowledge to auctions. Another memory is from a panel from the late 70s where several of our CS people, and I remember especially Rabin and Eli Shamir made predictions about the future of computers. While I expected predictions in the direction of AI and science fiction, both Michael and Eli made very “mundane” predictions about a revolution in availability of information, which to a large extent were on the mark!

  10. March 13, 2014 7:11 am

    Link correction:

    (Long proofs are not always the most important results).

    https://www.academia.edu/440527/VISUALIZATION_OF_THE_FOUR_COLOR_THEOREM

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

Follow

Get every new post delivered to your Inbox.

Join 1,688 other followers