Steven Rudich

Steven Rudich (born October 4, 1961 ) is an American computer scientist who deals with complexity theory , cryptography and combinatorics .

Rudich received his doctorate in 1989 from the University of California, Berkeley with Manuel Blum (Limits on the Provable Consequences of One-Way Functions) and has been Professor of Computer Science at Carnegie Mellon University since the early 1990s .

In 2007 he and Alexander Razborov received the Gödel Prize for the work Natural Proof , which showed that circuit complexity methods for determining a lower limit of the complexity of a problem are probably not suitable for solving the P-NP problem . In doing so, they isolate a common property of these circuit complexity methods, which they call natural proof . They showed that a natural proof proof for the P = NP problem would result in no pseudo-random number generators, which is generally accepted. They further showed that there is no natural proof evidence that some known cryptographic problems are NP-hard (such as the factorization of integers or the discrete logarithm problem). The work of Razborov and Rudich was an important advance in the P = NP problem, one of the Clay problems, which showed that one had to look in new directions for the solution.

He is editor of the Journal of Cryptography.

Rudich is an amateur magician.

Web links

• Homepage at Carnegie Mellon

Individual evidence

1. ^ Razborov, Rudich: Natural Proof. Journal of Computer and System Sciences, Vol. 55, 1997, pp. 24-35 and Proc. 26th Int. ACM Symposium on the Theory of Computing (STOC), 1994, p. 204, online here, Postscript file.