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 at the University of California, Berkeley with Manuel Blum ( Limits on the provable Consequences of One - Way Functions), and since the early 1990s, a professor of computer science at Carnegie Mellon University.

In 2007 he was awarded with Alexander Razborov the Gödel Prize for work Natural Proof that showed the circuit complexity methods are probably not suitable for the determination of a lower limit to the complexity of a problem, to solve the P- NP problem .. They isolate a common characteristic of these circuit complexity method, which they call Natural proof. They showed that a Natural Proof proof of the P = NP problem would have the consequence that no pseudo-random generators exist, but what is generally believed. Next, they showed that there is no natural proof evidence that some well-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 that showed that you had to look in new directions for the solution.

He is the editor of the Journal of Cryptography.

Rudich is amateur magician.