Nominator's project description
| Professor Levin is an internationally leading researcher in theoretical computer science. He is one of the co-founders of the theory of NP completeness, which today is part of the basic curriculum of virtually every computer science programme around the globe. Furthermore, he founded the theory of average case complexity and made fundamental contributions in areas such as algorithmic randomness, Kolmogorov complexity, interactive proof systems and cryptography. In Germany, he will work on algorithmic randomness and its relations to pseudorandomness. |
