Leonid Levin
O aluno de Kolmogorov que descobriu a NP-completude na União Soviética enquanto Stephen Cook fazia o mesmo no Ocidente, e que depois lançou as bases da teoria das funções unidirecionais.
Nascido em Dnipropetrovsk em 1948, Levin chegou aos seus resultados sobre problemas de busca universal no início dos anos 1970, mais ou menos em paralelo ao artigo de Cook de 1971. A publicação soviética era lenta e politicamente delicada, então o reconhecimento demorou; hoje o resultado é conhecido como teorema de Cook–Levin. Emigrou em 1978 e virou professor na Universidade de Boston.
Duas de suas contribuições importam mais para criptógrafos. Ele construiu uma função unidirecional universal: se existe alguma função unidirecional, a dele é uma — embora ninguém consiga provar nenhuma das duas metades. E, com Oded Goldreich, mostrou em 1989 que toda função unidirecional esconde um bit hardcore tão difícil de adivinhar quanto é difícil inverter a função. Isso virou peça da construção HILL uma década depois.