Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Clemens Lautemann

Expand Messages
  • 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
    Message 1 of 1 , Apr 30, 2005
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.