Steven Rudich

Steven Rudich (October 4, 1961 to October 29, 2024) was an American computational theorist and professor in the Carnegie Mellon School of Computer Science. In 1994, with Alexander Razborov, he proved that a large class of combinatorial arguments, called natural proofs, was unlikely to answer many important problems in computational complexity theory, work for which the two were awarded the 2007 Godel Prize. He also co-authored a paper showing that all then-known NP-complete problems remain NP-complete even under AC0 or NC0 reductions. Among Carnegie Mellon students he was best known as the teacher of Great Theoretical Ideas in Computer Science, often considered one of the hardest classes in the undergraduate curriculum. He was a longtime editor of the Journal of Cryptology and an accomplished magician; his Erdos number was 2.