Miller-Rabin primality test immediately came to mind. But apparently he improved Berlekamp's algorithm, and is responsible for the pumping lemma [1] as well.
I agree with other posters; Rabin deserves an HN black bar.
[1] Basically, the pumping lemma says if you feed a finite state machine a long enough input, the FSM must loop. You can delete the looping part of the input or insert extra copies of it; the FSM can't tell the difference, it has to give the same output. In theoretical computer science, the pumping lemma is usually introduced early, as the simplest example of a theorem that proves there are things that cannot be computed by a certain class of computing machines (FSMs).
3 comments
[ 3.3 ms ] story [ 22.1 ms ] threadI agree with other posters; Rabin deserves an HN black bar.
[1] Basically, the pumping lemma says if you feed a finite state machine a long enough input, the FSM must loop. You can delete the looping part of the input or insert extra copies of it; the FSM can't tell the difference, it has to give the same output. In theoretical computer science, the pumping lemma is usually introduced early, as the simplest example of a theorem that proves there are things that cannot be computed by a certain class of computing machines (FSMs).