It was announced these days that the 2012 Knuth Prize was awarded to Leonid A. Levin, a native of Dnepropetrovsk, an alumnus of Moscow Lomonosov State University, and a professor at Boston University.
From 1996 the Knuth Prize has been distinguishing individuals for their overall impact on computer science. The prize is awarded under the auspices of the two rather influential international organizations: the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory and IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing. The material part of the award includes 5000 dollars. The sum does not excite the imagination of the reader, and the occasion might seem pretty ordinary, since various awards in sciences are galore and it is practically impossible to trace all of them.
But every Knuth Prize is quite topical for anyone who has even a tiny bit of knowledge in informatics and programming. That is no wonder at all, for Donald Knuth is the alive guru who authored the multi-volume treatise The Art of Programming which has been the main textbook for practically all programmers of the modern era. Donald Knuth had gifted to the scientists of all specialities the celebrated programs TeX and Metafont for preparation of articles with scientific symbols. Knuth is an unmatched example of unselfish service to science and education. To see one's own name in the list of recipients of the Knuth Prize is an exceptional honor for every computer specialist.
The Knuth Prize is awarded for the overall contribution to science rather than a sole outstanding achievement. The 2012 Prize citation distinguishes the four decades of Levin's research in complexity theory, cryptography, and information theory which is always aimed to the future. It is emphasized that Levin is best known for his discovery of NP-completeness, the key notion of computational complexity. The discovery was made by Levin in the Soviet Union in 1971 independently of and simultaneously with Stephen Cook. The Cook–Levin Theorem has entered every textbook on computational complexity. The problem P=NP, related to the theorem, opens the list of the famous millennium problems of the Clay Mathematics Institute.
The supervisor of Levin was Andrey Kolmogorov. In 1971 Levin had submitted his Kandidat thesis, but it turned out impossible to arrange public maintenance in Moscow. The two reasons transpire behind this: the independent behavior of Levin was treated as political unreliability in the USSR, and the anti-Semitic views kept residence in the domestic mathematical establishment of those years. Kolmogorov asked his friend Sergey Sobolev, the founder and director of the Institute of Mathematics of the Siberian Division of the Academy of Sciences, to arrange the defence of Levin's thesis in Novosibirsk. Sobolev agreed but all of a sudden the thesis was rejected by secret ballot in spite of the positive official reviews by Nikolai Shanin, Boris Trakhtenbrot, and Yanis Bardzins. Unpredictably, the scientist who spoke against the thesis was one of those whose interests in mathematics were closest to Levin's research. During the public maintenance Levin was accused of having a “dim political face”—it turned out that mathematical filth had found the route from Moscow to Novosibirsk. Levin was not granted the Kandidat degree, and the attitude of various authorities to him had left much to be desired since then.
Describing those times, Levin mentioned: “I became a burden for all whom I had contacted, I was forbidden to work in serious scientific institutions, and I even felt embarrassed to attend scientific seminars since the participants were asked to inform of my presence.” Levin had been pressed out of mathematics and his native country.
Levin's outstanding scientific odyssey has successfully continued in the USA he had emigrated to in 1978, where he has found due conditions for happy work and life. Here he developed the theory of averaged-case NP-completeness. This theory still gives the best explanation of why bad computational problems are encountered in the average under relatively random choice of data rather than in some special situations. The list of Levin's achievements in America is impressive. Levin, together with László Babai, Lance Fortnow, and Mario Szegedy, suggested the concept of holographic proofs whose correctness can be checked by inspecting their small fractions. Suffice it to note that Levin and his coauthors solved a few puzzles of the today's cryptography.
There are many reasons to congratulate Leonid and feel proud of him and the world science. But it is impossible to get rid of sad feelings since the intellectual potential of our compatriot was uncalled-for in his homeland but gave rise to envy and expulsion. The bacilli of xenophobia, obstruction, self-appraisal, and isolation from the world are unbeatable in scientific life. To proceed without sanitation in science is impossible in much the same way as in medicine.
November 8, 2012
| English Page | Russian Page |