[Computational Complexity] Andrej (Andrey) Muchnik-a late memorial
- (Guest Post by Alexander Shen. Thanks to Lance for Suggesting it.)
Andrej (Andrey) Muchnik died unexpectly last March, but the news didn't spread out, so I am thankful to Lance Fortnow and Bill Gasarch who give me the opportunity to write a few words about him. His death was a sudden blow not only for his family (his parents, Albert A. Muchnik, of Muchnik - Friedberg solution of Post problem, and Nadezhda M. Ermolaeva; both were students of Petr S. Novikov; and his brother Ilya) but also for all his colleagues.
Andrej, whom I knew since our undergraduate studies, was not only the brilliant mathematician, but a deep thinker. He lived in his own world -- a very rich one that was not completely unrelated to a "real life" (i.e., the mess around us), but still clearly separated from it, and the interactions between these two worlds were quite difficult and often painful. His mathematical interests were driven by internal logic of the subject, not the current "fashion"; sometimes he rediscovered an old result not knowing about it; at some other times his results (being not published or published only in a short note) were rediscovered later by others. Probably his most known result is an elementary proof of Rabin's theorem (decidability of second-order monadic theory of two successors), invented while Andrej was a fourth-year student, and its generalizations; my personal favourite is one of his last results saying that for any strings A and B there is a string C such that |C| [length] is about K (A|B) [conditional Kolmogorov complexity]; K(C|A) is negligible and K (A|B,C) is negligible (all up to logarithmic terms).
a seminar in Moscow that was started by Kolmogorov himself; the work of this seminar and its participants was deeply influenced by Andrej, and I think that all we agree that most non-trivial ideas discussed in this seminar and most interesting results obtained by the participants of the seminar were due to Andrej (or at least inspired by him). Personally I am extremely grateful to him for all his support and encouragement and very sorry that I didn't tell this to him explicitly and didn't help him enough while he was alive.
See the seminar site note (both Russian and English) (written mostly by Andrej's teacher and friend, how helped him a lot, Alexey Semenov)
some papers of Andrej (not all -- we are still trying to prepare some unfinished papers for publication) can be found here
Posted By GASARCH to Computational Complexity at 9/25/2007 06:26:00 PM