What we have feared during the last weeks and months came true yesterday morning: Clemens Lautemann died at the age of 53 from cancer.Most recently Lautemann had been working on logical characterizations of complexity classes but I will remember him most for his beautiful proof (or here) that BPP, the class of languages with efficient probabilistical computatins, is in the second level of the polynomial-time hierarchy. In 1983 Sipser had shown BPP in the fourth level, and very soon after Gács and Lautemann independently showed BPP in the second level. Lautemann gave a very simple combinatorial proof that I consider one of the prettiest applications of the probabilistic method to complexity.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Saturday, April 30, 2005
Some sad news from Thomas Schwentick.
Post a Comment