This work is licensed under a
Creative Commons License.
|
Saturday, April 30, 2005
Clemens Lautemann
Posted by Lance
Some sad news from Thomas Schwentick.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.7:31 AM
# 0 comments
Links to this post:
Weblog Home
Archives
