Logic List Mailing Archive

Boris Trakhtenbrot (1921-2016)

From Lance Fortnow's blog:
http://blog.computationalcomplexity.org/2016/09/boris-trakhtenbrot-1921-2016.html

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.
--
[LOGIC] mailing list
http://www.dvmlg.de/mailingliste.html
Archive: http://www.illc.uva.nl/LogicList/

provided by a collaboration of the DVMLG, the Maths Departments in Bonn and Hamburg, and the ILLC at the Universiteit van Amsterdam