Leonid Levin’s career began in the Soviet Union, where he conducted pathbreaking work on computational complexity. Now a CAS Professor of Computer Science, Levin is a leader in the fields of cryptography theory and algorithmic information.
This month, he gave the Knuth Prize Lecture to a gathering of colleagues at the Symposium on Foundations of Computer Science in New Brunswick, NJ. The IEEE Computer Society, which sponsored the symposium, and the Association for Computing Machinery honored Levin with the 2012 Knuth Prize.
The Knuth Prize is named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms. Levin received this year’s prize for his visionary research in complexity, cryptography, and information theory, including the discovery of NP-completeness. Working in the Soviet Union at the same time as Stephen Cook in the United States, Levin made his discovery of NP-completeness, the core concept of computational complexity. This discovery best explains why many computational problems require prohibitively slow brute-force solutions. Levin also developed the theory of “average-case NP-completeness,” for problems considered intractable on average.
With co-authors Laszlo Babai, Lance Fortnow, and Mario Szegedy, Levin also provided a key step in the proof of the celebrated PCP Theorem, the cornerstone of the theory of computational hardness of approximation. It investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. Together, this team proposed the notion of “holographic proofs,” whose correctness can be checked efficiently by a program that samples only a small fraction of the bits.
In cryptography theory, Levin co-authored the “Goldreich-Levin hardcore bit” with Oded Goldreich, which has become an essential ingredient in many subsequent key results to establish improved security. He also changed the landscape of Kolmogorov complexity, a modern notion of randomness dealing with the quantity of information in individual objects. Andrey Kolmogorov, a Russian mathematician, was Levin’s doctoral advisor at Moscow University. Levin’s advances have become essential tools in the research area of algorithmic information.