8 ms·

Michael Rabin has died

414 points by tkhattra 6mo ago

adrian_b 6mo ago
Michael O. Rabin had important contributions in many domains, but from a practical point of view the most important are his contributions to cryptography. After Ralph Merkle, Whitfield Diffie and Martin Hellman, Michael O. Rabin is the most important of the creators of public-key cryptography. The RSA team (Ron Rivest, Adi Shamir and Leonard Adleman) is better known than Michael O. Rabin, but that is entirely due to marketing and advertising, because they founded a successful business. In reality the RSA algorithm is superfluous and suboptimal. If the RSA team had never discovered this algorithm, that would have had a null impact on the practice of cryptography. Public-key cryptography would have been developed equally well, because the algorithms discovered by Merkle, Diffie, Hellman and Rabin are necessary and sufficient. On the other hand, while without the publications of RSA, cryptography would have evolved pretty much in the same way, without the publications of Michael O. Rabin from the late seventies the development of public-key cryptography would have been delayed by some years, until someone else would have made the same discoveries. Together with Ralph Merkle, Michael O. Rabin was the one who discovered the need for secure cryptographic hash functions, i.e. one-way hash functions, which are now critical for many applications, including digital signatures. Thus Rabin is the one who has shown how the previously proposed methods of digital signing must be used in practice. For example, the original signing algorithm proposed by RSA could trivially be broken and it became secure only in the modified form described by Rabin, i.e. with the use of a one-way hash function. Originally, Merkle defined 2 conditions for one-way hash functions, of resistance to first preimage attacks and second preimage attacks, while Rabin defined 1 condition, of resistance to collision attacks. Soon after that it was realized that all 3 conditions are mandatory, so the 2 definitions, of Merkle and of Rabin, have been merged into the modern definition of such hash functions. Unfortunately, both Merkle and Rabin have overlooked a 4th condition, of resistance to length extension attacks. This should have always been included in the definition of secure hash functions. Because this 4th condition was omitted, the US Secure Hash Algorithm Standards defined algorithms that lack this property, which has forced many applications to use workarounds, like the HMAC algorithm, which for many years have wasted time and energy wherever encrypted communications were used, until more efficient authentication methods have been standardized, which do not use one-way hash functions, for instance GCM, which is today the most frequently used authentication algorithm on the Internet.
- blondie9x 6mo ago
  [flagged]
  - adrian_b 6mo ago
    This is no AI slop. On the contrary, you cannot find frequently descriptions about the role of Michael O. Rabin in the creation of public-key cryptography, so few people are aware of it and I bet that no AI model can generate any text even remotely resembling this, because this information cannot be found in any single place in the possible training texts. You can find definitions of secure hash functions everywhere, but pretty much nowhere you will find who are the authors of the conditions that are used in the modern definition and who have introduced the use of one-way hash functions. I did not find this information anywhere, before reading the original publications of Rabin and Merkle from 1978/1979 and some later follow-up papers written by them. You will not find this historical information in Wikipedia and I believe that it is important to know who are the true authors of the things that one uses daily. Connecting to this site or to any other site with https uses digital signatures that depend on the collision-resistant hash functions defined by Rabin and Merkle. The Wikipedia article about Michael O. Rabin lists many of his achievements, but all those that are listed there are much less important than his contribution to the definition of the one-way hash functions, which lead to secure digital signatures. Wikipedia mentions only the Rabin signature algorithm, but that has negligible importance, because it has been used only very rarely. On the other hand all other signature algorithms are based on the work of Rabin, by using secure hash functions.
  - Findecanor 6mo ago
    I don't think that is AI slop. adrian_b often post long posts because he thinks he has a lot to say, but you can often tell that they contain his personal views and points that he thinks are important related to the discussions whereas actual AI slop tends to be bland and generic.
  - d-cc 6mo ago
    I wouldn’t really call that AI slop. Some people just write longer posts because they’ve got a lot they want to get across, and you can usually tell it reflects their own opinions and what they think matters in the discussion. Actual AI-generated stuff tends to come off more generic and lacks that personal angle. I really enjoyed reading it.
thraxil 6mo ago
I took his Introduction to Cryptography class when he was a visiting professor at Columbia. Absolute master of an old-school chalkboard lecturer. They don't make them like that any more.
- medina 6mo ago
  Hugely engaging, the margins of my notebook had many of his quips… there was an archive online somewhere. e.g., x minus x is zero, even for Euler, so therefore… Found on Archive, https://web.archive.org/web/20210509160248/http://www.eecs.harvard.edu/~cat/rabinisms.html https://web.archive.org/web/20210509160248/http://www.eecs.h...
- arbuge 6mo ago
  I know him from Harvard and came here to say pretty much the same thing. RIP.
  - ishi 6mo ago
    I took his Computability class in the Hebrew University. He got angry that students were often late to class, and said that this never happened in Harvard...
    - ignoramous 6mo ago
      Any of his "chalkboard" lectures (preferably in English) in open archives of these universities? YouTube searches only bring up Prof Rabin's lectures aided by slides and presentation (ex: https://www.youtube.com/watch?v=thK_qJqx5mo https://www.youtube.com/watch?v=thK_qJqx5mo at Tel Aviv Uni / https://www.youtube.com/watch?v=QCX0Ut0hcWw https://www.youtube.com/watch?v=QCX0Ut0hcWw at Harvard).
      - YZF 6mo ago
        There's a chalkboard here (used ~44:50): Cryptography and Preventing Collusion in Second Price (Vickery) Auctions - Michael Rabin https://www.youtube.com/watch?v=4cmCBVrVQqc https://www.youtube.com/watch?v=4cmCBVrVQqc No chalkboard but more lectures https://youtu.be/nbePExzSTQ0?si=KkTbwfwj5rMtQUhD&t=681 https://youtu.be/nbePExzSTQ0?si=KkTbwfwj5rMtQUhD&t=681 - פלאי תורת ההצפנות ויישומיה לתהליכים פיננסיים (The wonders of cryptography and financial applications) https://www.youtube.com/watch?v=N_LG5Hcc8mM https://www.youtube.com/watch?v=N_LG5Hcc8mM - Lecture 7 - Zero Knowledge Proofs and Applications Michael Rabin For those interested in searching for more here's a Hebrew search string you can use: "פרופסור מיכאל רבין הרצאה" interesting enough Google and YT search yield results in English and Hebrew but possibly different ones than just searching in English. EDIT: One more: https://www.youtube.com/watch?v=30wkb46BE1k https://www.youtube.com/watch?v=30wkb46BE1k
opem 6mo ago
It's hard to imagine how a single person managed to accomplish so much. RIP to the great soul :|
- tclancy 6mo ago
  Seriously. After reading, I scrolled through his Known For section and thought, “Alright already, leave something for everybody else to work on.”
puttycat 6mo ago
@dang this deserves a black ribbon
- d-cc 6mo ago
  What is a black ribbon?
  - vardump 6mo ago
    Probably meant black HN top bar.
  - dredmorbius 6mo ago
    An HN website tweak as a sign of respect on the passing of notable contributors to the tech world: <https://blog.willmeye.rs/whos-received-a-black-bar/ https://blog.willmeye.rs/whos-received-a-black-bar/>
- wk_end 6mo ago
  "@dang" doesn't do anything last I heard (though at this point it's used often enough that maybe the HN folks should consider it). If you want to reach the mods you can contact hn@ycombinator.com I believe.
  - eranation 6mo ago
    I did.
snitty 6mo ago
May his memory be a blessing.
AlecBG 6mo ago
First sentence starts with horrible antisemitism. Can someone fix it? (on my phone with kids so not in a position to)
- codingrightnow 6mo ago
  It's been fixed.
  - fakedang 6mo ago
    Still up. Looks like this is going to be another game of hit the hedgehog.
    - metmac 6mo ago
      People keep adding different slurs. Awful and disgraceful.
      - riddlemethat 6mo ago
        Anti-Jew rhetoric is at a level unseen since WW2. It’s the new normal. It’s horrible.
        dbwkdofpqndjflf 6mo ago
        Yeah, I come into contact with some form of Jewish hate on a literal daily basis now. It’s been this way for months.
        nothrabannosir 6mo ago
        *It’s the old normal :(
        ajewhere 6mo ago
        [flagged]
        6mo ago
deleted 6mo ago
[deleted]
XCSme 6mo ago
I loved implementing the Rabin-Karp algoritm, such a fun and celever solution.
maxtaco 6mo ago
Amazing man, with many important contributions over a very long career. The Rabin Cryptosystem (like RSA, but with public exponent 2) is notable for two reasons. First, unlike RSA, it is provably as hard as "factorization" (as he would call it), and second, unlike RSA, it wasn't protected by patent.
xorvoid 6mo ago
Thank you Michael Rabin for your excellent work. Rest in Peace. Rabin Fingerprinting is one of my favorites of his contributions. It's a "rolling hash" that allows you to quickly compute a 32-bit (or larger) hash at *every* byte offset of a file. It is used most notably to do file block matching/deduplication when those matching blocks can be at any offset. It's tragically underappreciated. I've been meaning to write up a tutorial as part of my Galois Field series. Someday.. Thank you again!
- jonhohle 6mo ago
  I recently found his fingerprint algorithm and wrote a utility that uses it to find duplicate MIPS code for decompilation[0] and build unique identifiers that can be used to find duplicates without sharing any potentially copyrighted data[1]. This replaced some O(n²) searches through ASCII text, reducing search time from dozens of seconds to fractions of a second. 0 - https://github.com/ttkb-oss/mipsmatch https://github.com/ttkb-oss/mipsmatch 1 - https://github.com/ttkb-oss/mipsmatch/wiki/Identifiers https://github.com/ttkb-oss/mipsmatch/wiki/Identifiers
- __MatrixMan__ 6mo ago
  I'm working on a data annotation system based around Rabin fingerprints. They're a really neat idea. I especially like how if you end up with hash characteristics that you don't like, your can just select a different irreducible Galois polynomial and now you've got a whole new hash algorithm. It's like tuning to a different frequency. For me it means I don't have to worry about cases where there aren't enough nearby fingerprints for the annotation to adhere to, I can just add or remove polynomials until I get a good density.
- vlovich123 6mo ago
  Important to note that FastCDC is about an order of magnitude for block deduplication and is generally considered the state of art for such an approach (speed of computing the hash is more important than absolutely optimal distribution of hashes).
- syncsynchalt 6mo ago
  That's where I knew the name from. Thank you! I wrote a Rabin—Karp implementation in ~2006 as part of the spam and threat scanning stack for the MX Logic mail service. It was incredibly performant, letting us test {n} bytes against an essentially unlimited number of string signatures in O(n) time.
sidcool 6mo ago
Doctoral advisor - Alonzo Church
- eranation 6mo ago
  TIL. Also just realized that Alan Turing was also one of Church’s doctoral students. We stand on the shoulders of these giants.
moralestapia 6mo ago
"As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher." Interesting. Some people are lucky enough to find their vocation quite early in life.
- redwood 6mo ago
  Wow hadn't heard of him https://en.wikipedia.org/wiki/Elisha_Netanyahu https://en.wikipedia.org/wiki/Elisha_Netanyahu
  - moralestapia 6mo ago
    Yeah. Everything is intertwined at some level. Interesting.
    - k4rli 6mo ago
      [flagged]
  - myth_drannon 6mo ago
    What a small world. But the entire extended family are professors. Too bad one became a politician.
    - keybored 6mo ago
      Benzion? > Benzion Netanyahu ... A scholar of Judaic history, he was also an activist in the Revisionist Zionism movement, who lobbied in the United States to support the creation of the Jewish state.
      - beagle3 6mo ago
        Benzion’s son (and Elisha’s nephew) Benjamin Netanyahu is the Israeli prime minister.
ontouchstart 6mo ago
Michael Rabin, 1976 ACM Turing Award Recipient https://youtu.be/L3FZzGU3n14 https://youtu.be/L3FZzGU3n14
- seism 6mo ago
  That sly remark at 22:40 on the telephone ringing :)
- ignoramous 6mo ago
  Michael Rabin: "godfather of Israeli computer science", https://www.ynetnews.com/health_science/article/byohxvw611l https://www.ynetnews.com/health_science/article/byohxvw611l
mclightning 6mo ago
[flagged]
peterbonney 6mo ago
I had the incredible good fortune to take one of his classes in college, and I loved it so much I took another just to learn from him again. A tremendous intellect AND an incredibly engaging and talented instructor. It would be an exaggeration to say that I knew him, but nevertheless he had a great impact on my education and my life. He will be missed.
BrianneLee011 6mo ago
A founding father of computer science has passed away. Thank you for building the foundations that made modern AI possible.
gchallen 6mo ago
I took a course from him as a graduate student. I was not (and am still not) a theoretician. But I enjoyed the class and Professor Rabin's lectures. A friend of mine was one of his graduate students and a teaching assistant for the class. He pointed out to me once that Professor Rabin would state many of his points during lecture twice. Once I started listening more carefully, I found this to be true. It was both subtle and pedagogically effective. English was not his first language, but he enjoyed his struggles with it. I remember him stumbling over the pronunciation of a word during class. Giving up with a smile, he said, "This is a word I know only from books."
LePetitPrince 6mo ago
[dead]
pcblues 6mo ago
Before AI and the swell of papers for money(tenure), not necessarily in that order, science mattered. As a result, the science mattered more in the past. RIP Rabin.
inglor_cz 6mo ago
Born in Breslau, nowadays Wroclaw. Had enough of a luck that his parents escaped Germany before the war. Many other people weren't as prescient... Also, as a teen he was taught mathematics by a certain Elisha Netanyahu, who was an uncle of the current Israeli Prime Minister. What an unexpected connection, at least for me.
jason_s 6mo ago
I am 90% finished writing an article about Miller-Rabin primality testing. A few weeks ago I was looking around and found out that Rabin was still alive, which I hadn't expected... and was wondering if I should try to contact him to ask a few questions regarding his motivation to explore stochastic algorithms. Too late. :-( We are all in his debt.
MassPikeMike 5mo ago
This collection of "Rabinisms" [1] (thanks to the Internet Archive for keeping it from being lost) can give you some of the flavor of the delightful experience that it was to take one of his classes. RIP. [If P = NP,] then all of modern cryptography collapses. On this happy thought... (1998-11-24) I'm one of those people who is just never wrong. I mean, not one of those people. I'm like everybody else. Nobody is ever wrong. (1998-12-08) After all I said, put here the word "obvious". (1998-12-15) I am going to show that in one round the probability of not reaching agreement is less or equal to 2. ... Yeah, we're establishing new ground in probability theory. (1998-12-17) It's more than 10 years old. It's either classical or incorrect. (Fall 1998) [1] https://web.archive.org/web/20210509160248/http://www.eecs.harvard.edu/~cat/rabinisms.html https://web.archive.org/web/20210509160248/http://www.eecs.h...

414 points by tkhattra 6mo ago

Michael O. Rabin had important contributions in many domains, but from a practical point of view the most important are his contributions to cryptography. After Ralph Merkle, Whitfield Diffie and Martin Hellman, Michael O. Rabin is the most important of the creators of public-key cryptography. The RSA team (Ron Rivest, Adi Shamir and Leonard Adleman) is better known than Michael O. Rabin, but that is entirely due to marketing and advertising, because they founded a successful business. In reality the RSA algorithm is superfluous and suboptimal. If the RSA team had never discovered this algorithm, that would have had a null impact on the practice of cryptography. Public-key cryptography would have been developed equally well, because the algorithms discovered by Merkle, Diffie, Hellman and Rabin are necessary and sufficient. On the other hand, while without the publications of RSA, cryptography would have evolved pretty much in the same way, without the publications of Michael O. Rabin from the late seventies the development of public-key cryptography would have been delayed by some years, until someone else would have made the same discoveries. Together with Ralph Merkle, Michael O. Rabin was the one who discovered the need for secure cryptographic hash functions, i.e. one-way hash functions, which are now critical for many applications, including digital signatures. Thus Rabin is the one who has shown how the previously proposed methods of digital signing must be used in practice. For example, the original signing algorithm proposed by RSA could trivially be broken and it became secure only in the modified form described by Rabin, i.e. with the use of a one-way hash function. Originally, Merkle defined 2 conditions for one-way hash functions, of resistance to first preimage attacks and second preimage attacks, while Rabin defined 1 condition, of resistance to collision attacks. Soon after that it was realized that all 3 conditions are mandatory, so the 2 definitions, of Merkle and of Rabin, have been merged into the modern definition of such hash functions. Unfortunately, both Merkle and Rabin have overlooked a 4th condition, of resistance to length extension attacks. This should have always been included in the definition of secure hash functions. Because this 4th condition was omitted, the US Secure Hash Algorithm Standards defined algorithms that lack this property, which has forced many applications to use workarounds, like the HMAC algorithm, which for many years have wasted time and energy wherever encrypted communications were used, until more efficient authentication methods have been standardized, which do not use one-way hash functions, for instance GCM, which is today the most frequently used authentication algorithm on the Internet.

blondie9x 6mo ago
[flagged]
- adrian_b 6mo ago
  This is no AI slop. On the contrary, you cannot find frequently descriptions about the role of Michael O. Rabin in the creation of public-key cryptography, so few people are aware of it and I bet that no AI model can generate any text even remotely resembling this, because this information cannot be found in any single place in the possible training texts. You can find definitions of secure hash functions everywhere, but pretty much nowhere you will find who are the authors of the conditions that are used in the modern definition and who have introduced the use of one-way hash functions. I did not find this information anywhere, before reading the original publications of Rabin and Merkle from 1978/1979 and some later follow-up papers written by them. You will not find this historical information in Wikipedia and I believe that it is important to know who are the true authors of the things that one uses daily. Connecting to this site or to any other site with https uses digital signatures that depend on the collision-resistant hash functions defined by Rabin and Merkle. The Wikipedia article about Michael O. Rabin lists many of his achievements, but all those that are listed there are much less important than his contribution to the definition of the one-way hash functions, which lead to secure digital signatures. Wikipedia mentions only the Rabin signature algorithm, but that has negligible importance, because it has been used only very rarely. On the other hand all other signature algorithms are based on the work of Rabin, by using secure hash functions.
- Findecanor 6mo ago
  I don't think that is AI slop. adrian_b often post long posts because he thinks he has a lot to say, but you can often tell that they contain his personal views and points that he thinks are important related to the discussions whereas actual AI slop tends to be bland and generic.
- d-cc 6mo ago
  I wouldn’t really call that AI slop. Some people just write longer posts because they’ve got a lot they want to get across, and you can usually tell it reflects their own opinions and what they think matters in the discussion. Actual AI-generated stuff tends to come off more generic and lacks that personal angle. I really enjoyed reading it.

thraxil 6mo ago

I took his Introduction to Cryptography class when he was a visiting professor at Columbia. Absolute master of an old-school chalkboard lecturer. They don't make them like that any more.

medina 6mo ago
Hugely engaging, the margins of my notebook had many of his quips… there was an archive online somewhere. e.g., x minus x is zero, even for Euler, so therefore… Found on Archive, https://web.archive.org/web/20210509160248/http://www.eecs.harvard.edu/~cat/rabinisms.html https://web.archive.org/web/20210509160248/http://www.eecs.h...
arbuge 6mo ago
I know him from Harvard and came here to say pretty much the same thing. RIP.
- ishi 6mo ago
  I took his Computability class in the Hebrew University. He got angry that students were often late to class, and said that this never happened in Harvard...
  - ignoramous 6mo ago
    Any of his "chalkboard" lectures (preferably in English) in open archives of these universities? YouTube searches only bring up Prof Rabin's lectures aided by slides and presentation (ex: https://www.youtube.com/watch?v=thK_qJqx5mo https://www.youtube.com/watch?v=thK_qJqx5mo at Tel Aviv Uni / https://www.youtube.com/watch?v=QCX0Ut0hcWw https://www.youtube.com/watch?v=QCX0Ut0hcWw at Harvard).
    - YZF 6mo ago
      There's a chalkboard here (used ~44:50): Cryptography and Preventing Collusion in Second Price (Vickery) Auctions - Michael Rabin https://www.youtube.com/watch?v=4cmCBVrVQqc https://www.youtube.com/watch?v=4cmCBVrVQqc No chalkboard but more lectures https://youtu.be/nbePExzSTQ0?si=KkTbwfwj5rMtQUhD&t=681 https://youtu.be/nbePExzSTQ0?si=KkTbwfwj5rMtQUhD&t=681 - פלאי תורת ההצפנות ויישומיה לתהליכים פיננסיים (The wonders of cryptography and financial applications) https://www.youtube.com/watch?v=N_LG5Hcc8mM https://www.youtube.com/watch?v=N_LG5Hcc8mM - Lecture 7 - Zero Knowledge Proofs and Applications Michael Rabin For those interested in searching for more here's a Hebrew search string you can use: "פרופסור מיכאל רבין הרצאה" interesting enough Google and YT search yield results in English and Hebrew but possibly different ones than just searching in English. EDIT: One more: https://www.youtube.com/watch?v=30wkb46BE1k https://www.youtube.com/watch?v=30wkb46BE1k

opem 6mo ago

It's hard to imagine how a single person managed to accomplish so much. RIP to the great soul :|

tclancy 6mo ago
Seriously. After reading, I scrolled through his Known For section and thought, “Alright already, leave something for everybody else to work on.”

puttycat 6mo ago

@dang this deserves a black ribbon

d-cc 6mo ago
What is a black ribbon?
- vardump 6mo ago
  Probably meant black HN top bar.
- dredmorbius 6mo ago
  An HN website tweak as a sign of respect on the passing of notable contributors to the tech world: <https://blog.willmeye.rs/whos-received-a-black-bar/ https://blog.willmeye.rs/whos-received-a-black-bar/>
wk_end 6mo ago
"@dang" doesn't do anything last I heard (though at this point it's used often enough that maybe the HN folks should consider it). If you want to reach the mods you can contact hn@ycombinator.com I believe.
- eranation 6mo ago
  I did.

snitty 6mo ago

May his memory be a blessing.

AlecBG 6mo ago

First sentence starts with horrible antisemitism. Can someone fix it? (on my phone with kids so not in a position to)

codingrightnow 6mo ago
It's been fixed.
- fakedang 6mo ago
  Still up. Looks like this is going to be another game of hit the hedgehog.
  - metmac 6mo ago
    People keep adding different slurs. Awful and disgraceful.
    - riddlemethat 6mo ago
      Anti-Jew rhetoric is at a level unseen since WW2. It’s the new normal. It’s horrible.
      - dbwkdofpqndjflf 6mo ago
        Yeah, I come into contact with some form of Jewish hate on a literal daily basis now. It’s been this way for months.
      - nothrabannosir 6mo ago
        *It’s the old normal :(
      - ajewhere 6mo ago
        [flagged]
        6mo ago

deleted 6mo ago

[deleted]

XCSme 6mo ago

I loved implementing the Rabin-Karp algoritm, such a fun and celever solution.

maxtaco 6mo ago

Amazing man, with many important contributions over a very long career. The Rabin Cryptosystem (like RSA, but with public exponent 2) is notable for two reasons. First, unlike RSA, it is provably as hard as "factorization" (as he would call it), and second, unlike RSA, it wasn't protected by patent.

xorvoid 6mo ago

Thank you Michael Rabin for your excellent work. Rest in Peace. Rabin Fingerprinting is one of my favorites of his contributions. It's a "rolling hash" that allows you to quickly compute a 32-bit (or larger) hash at *every* byte offset of a file. It is used most notably to do file block matching/deduplication when those matching blocks can be at any offset. It's tragically underappreciated. I've been meaning to write up a tutorial as part of my Galois Field series. Someday.. Thank you again!

jonhohle 6mo ago
I recently found his fingerprint algorithm and wrote a utility that uses it to find duplicate MIPS code for decompilation[0] and build unique identifiers that can be used to find duplicates without sharing any potentially copyrighted data[1]. This replaced some O(n²) searches through ASCII text, reducing search time from dozens of seconds to fractions of a second. 0 - https://github.com/ttkb-oss/mipsmatch https://github.com/ttkb-oss/mipsmatch 1 - https://github.com/ttkb-oss/mipsmatch/wiki/Identifiers https://github.com/ttkb-oss/mipsmatch/wiki/Identifiers
__MatrixMan__ 6mo ago
I'm working on a data annotation system based around Rabin fingerprints. They're a really neat idea. I especially like how if you end up with hash characteristics that you don't like, your can just select a different irreducible Galois polynomial and now you've got a whole new hash algorithm. It's like tuning to a different frequency. For me it means I don't have to worry about cases where there aren't enough nearby fingerprints for the annotation to adhere to, I can just add or remove polynomials until I get a good density.
vlovich123 6mo ago
Important to note that FastCDC is about an order of magnitude for block deduplication and is generally considered the state of art for such an approach (speed of computing the hash is more important than absolutely optimal distribution of hashes).
syncsynchalt 6mo ago
That's where I knew the name from. Thank you! I wrote a Rabin—Karp implementation in ~2006 as part of the spam and threat scanning stack for the MX Logic mail service. It was incredibly performant, letting us test {n} bytes against an essentially unlimited number of string signatures in O(n) time.

sidcool 6mo ago

Doctoral advisor - Alonzo Church

eranation 6mo ago
TIL. Also just realized that Alan Turing was also one of Church’s doctoral students. We stand on the shoulders of these giants.

moralestapia 6mo ago

"As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher." Interesting. Some people are lucky enough to find their vocation quite early in life.

redwood 6mo ago
Wow hadn't heard of him https://en.wikipedia.org/wiki/Elisha_Netanyahu https://en.wikipedia.org/wiki/Elisha_Netanyahu
- moralestapia 6mo ago
  Yeah. Everything is intertwined at some level. Interesting.
  - k4rli 6mo ago
    [flagged]
- myth_drannon 6mo ago
  What a small world. But the entire extended family are professors. Too bad one became a politician.
  - keybored 6mo ago
    Benzion? > Benzion Netanyahu ... A scholar of Judaic history, he was also an activist in the Revisionist Zionism movement, who lobbied in the United States to support the creation of the Jewish state.
    - beagle3 6mo ago
      Benzion’s son (and Elisha’s nephew) Benjamin Netanyahu is the Israeli prime minister.

ontouchstart 6mo ago

Michael Rabin, 1976 ACM Turing Award Recipient https://youtu.be/L3FZzGU3n14 https://youtu.be/L3FZzGU3n14

seism 6mo ago
That sly remark at 22:40 on the telephone ringing :)
ignoramous 6mo ago
Michael Rabin: "godfather of Israeli computer science", https://www.ynetnews.com/health_science/article/byohxvw611l https://www.ynetnews.com/health_science/article/byohxvw611l

mclightning 6mo ago

[flagged]

peterbonney 6mo ago

I had the incredible good fortune to take one of his classes in college, and I loved it so much I took another just to learn from him again. A tremendous intellect AND an incredibly engaging and talented instructor. It would be an exaggeration to say that I knew him, but nevertheless he had a great impact on my education and my life. He will be missed.

BrianneLee011 6mo ago

A founding father of computer science has passed away. Thank you for building the foundations that made modern AI possible.

gchallen 6mo ago

I took a course from him as a graduate student. I was not (and am still not) a theoretician. But I enjoyed the class and Professor Rabin's lectures. A friend of mine was one of his graduate students and a teaching assistant for the class. He pointed out to me once that Professor Rabin would state many of his points during lecture twice. Once I started listening more carefully, I found this to be true. It was both subtle and pedagogically effective. English was not his first language, but he enjoyed his struggles with it. I remember him stumbling over the pronunciation of a word during class. Giving up with a smile, he said, "This is a word I know only from books."

LePetitPrince 6mo ago

[dead]

pcblues 6mo ago

Before AI and the swell of papers for money(tenure), not necessarily in that order, science mattered. As a result, the science mattered more in the past. RIP Rabin.

inglor_cz 6mo ago

Born in Breslau, nowadays Wroclaw. Had enough of a luck that his parents escaped Germany before the war. Many other people weren't as prescient... Also, as a teen he was taught mathematics by a certain Elisha Netanyahu, who was an uncle of the current Israeli Prime Minister. What an unexpected connection, at least for me.

jason_s 6mo ago

I am 90% finished writing an article about Miller-Rabin primality testing. A few weeks ago I was looking around and found out that Rabin was still alive, which I hadn't expected... and was wondering if I should try to contact him to ask a few questions regarding his motivation to explore stochastic algorithms. Too late. :-( We are all in his debt.

MassPikeMike 5mo ago

This collection of "Rabinisms" [1] (thanks to the Internet Archive for keeping it from being lost) can give you some of the flavor of the delightful experience that it was to take one of his classes. RIP. [If P = NP,] then all of modern cryptography collapses. On this happy thought... (1998-11-24) I'm one of those people who is just never wrong. I mean, not one of those people. I'm like everybody else. Nobody is ever wrong. (1998-12-08) After all I said, put here the word "obvious". (1998-12-15) I am going to show that in one round the probability of not reaching agreement is less or equal to 2. ... Yeah, we're establishing new ground in probability theory. (1998-12-17) It's more than 10 years old. It's either classical or incorrect. (Fall 1998) [1] https://web.archive.org/web/20210509160248/http://www.eecs.harvard.edu/~cat/rabinisms.html https://web.archive.org/web/20210509160248/http://www.eecs.h...