[Computational Complexity] Clemens Lautemann
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 application of the probabilistic method to complexity.
Posted by Lance to Computational Complexity at 4/30/2005 07:31:00 AM