Citation | Michael Rabin is a founding figure of computer science. His early influential paper with Dana Scott introduced the notion of nondeterminism. He played a foundational role in the creation of complexity theory through his axiomatic treatment of the difficulty of computations. He proved fundamental results on the existence and complexity of decision procedures in mathematical logic. He pioneered randomization in algorithms, and devised important applications to testing primality, to reaching agreement in distributed systems and, with Richard Karp, to pattern matching. He had a deep influence on modern cryptography through his work on randomized algorithms and provably secure cryptographic methods. |