Thursday, September 22, 2016

Boris Trakhtenbrot (1921-2016)

I woke up this morning to two pieces of news. Subhash Khot has just been named a MacArthur Fellow, the "genius" award, for his work on unique games. But I also just learned about Monday's passing of the great Russian theorist Boris Trakhtenbrot at the age of 95.

Trakhtenbrot has a number of important results in automata theory, model theory and logic to name just a few areas. In computational complexity we know him best for the Gap Theorem which he proved independently with Allan Borodin. Roughly the gap theorem states that for any computable f there is a computable time-bound t such that DTIME(t) = DTIME(f(t)), every problem solvable in time f(t) can also be solved in time t. For example there is a time bound t such that DTIME(t) = DTIME(2t). This doesn't violate the time hierarchy since t may not be time-constructible. There is nothing special about time here, it works for space or any abstract complexity measure.

Borodin and Trakhtenbrot worked independently because they sat on different sides of the iron curtain during the cold war which very little communication in between. Boris Trakhtenbrot wrote A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (PDF) that traces this early history of Russian theory. He didn't hold back discussing some of the academic politics in Russia that stifled research into computational complexity and gave us a window into the Russian scientific community in the mid-20th century.

Thankfully the iron curtain has been replaced by a global internet and we can do science together. Let's hope it stays that way.

No comments:

Post a Comment