Steven Rudich , narozen dne4. října 1961, je americký počítačový teoretik, který pracuje v teorii složitosti , kryptografii a kombinatorice .
Rudich získal Ph. D. v roce 1989 z University of California, Berkeley pod dohledem Manuel Blum ( „Limity prokazatelné následky Jednosměrné funkce “). Od počátku 90. let je profesorem počítačové vědy na Carnegie-Mellon University .
V roce 2007 spolu s Alexandrem Razborov , dostal na cenu Gödel . pro jejich článek Natural Proof , kde se ukazuje, že redukční metody používané v komplexitě obvodů pravděpodobně nejsou vhodné pro řešení problému P = NP . Z tohoto důvodu zvýrazňují vlastnosti společné všem důkazům o snížení složitosti obvodů a nazývají důkazy s těmito vlastnostmi přirozenými důkazy . Ukazují, že přirozený důkaz problému P = NP by znamenal, že neexistují žádné pseudonáhodné generátory, jejichž existence je obecně připuštěna. Nakonec prokazují, že neexistuje žádný přirozený důkaz, který by prokázal, že některé známé kryptografické problémy (jako je faktorizace přirozených celých čísel nebo problém diskrétního logaritmu) jsou NP obtížné . Rudich je také spoluautorem článku, který dokazuje, že NP-úplné problémy přetrvávají i při redukci třídy AC 0 nebo NC 0 .
Rudich organizuje od roku 1991 letní vzdělávací program pro studenty středních škol . Ráno se hodiny zabývají různými aspekty teoretické informatiky a odpoledne jsou doplněny volitelnými aktivitami: robotika, programování, matematika. Vstupné je výběrem zkouškou zvanou úrokový test . Tento sedmitýdenní letní program, dříve nazývaný Andrew's Leap , se nyní nazývá Leap @ CMU .
Rudich je také amatérský kouzelník.