Steven Rudich , doğdu4 Ekim 1961, karmaşıklık teorisi , kriptografi ve kombinatorik alanlarında çalışan Amerikalı bir bilgisayar teorisyeni .
Rudich bir elde doktora 1989 yılında gelen Berkeley'deki California Üniversitesi'nden gözetiminde Manuel Blum ( "Tek Yönlü İşlevleri Kanıtlanabilir Consequences Sınırları "). 1990'ların başından beri Carnegie-Mellon Üniversitesi'nde bilgisayar bilimi profesörüdür .
2007 yılında, birlikte Alexandre Razborov , aldığı Gödel Ödülü . Devre karmaşıklığında kullanılan indirgeme yöntemlerinin muhtemelen P = NP problemini çözmek için uygun olmadığı gösterilen Natural Proof makalesi için . Bunun için, devre karmaşıklığını azaltmanın tüm kanıtlarında ortak olan özellikleri vurgularlar ve bu özelliklere sahip ispatları doğal ispatlar olarak adlandırırlar . P = NP sorununun doğal bir ispatının, sözde rasgele üreteçlerin bulunmadığını ima edeceğini gösterirler, varoluş genellikle kabul edilir. Son olarak, bilinen bazı kriptografik problemlerin (doğal tam sayıların çarpanlara ayrılması veya ayrık logaritma problemi gibi) NP açısından zor olduğunu kanıtlamak için doğal bir kanıt olmadığını gösterirler . Rudich, aynı zamanda, NP-tam sorunların AC 0 veya NC 0 sınıfındaki bir azalma altında bile aynı kaldığını kanıtlayan bir makalenin ortak yazarıdır .
Rudich 1991 yılından beri lise öğrencileri için bir yaz eğitim programı düzenliyor . Dersler sabahları teorik bilgisayar biliminin çeşitli yönlerini ele alır ve öğleden sonraları isteğe bağlı etkinliklerle tamamlanır: robotik, programlama, matematik. Kabul, faiz testi adı verilen sınavla seçilerek yapılır . Daha önce Andrew's Leap olarak adlandırılan bu yedi haftalık yaz programının adı artık Leap @ CMU .
Rudich aynı zamanda amatör bir sihirbazdır.