Allan Borodin on Theoretical Computer Science

Allan Borodin is vising the Microsoft Research Theory group this week, and this morning we are sharing the same office. I took that opportunity to ask him a few questions.

[Claire:] I saw on a blog that you were the only attendee at FCRC who was already present at the first STOC conference. Of course there are many other active researchers whose work also spans the same time interval, but they were not at FCRC this year, and they are not in my office right now. So, for you, who have perspective on the evolution of the field over its entire history, what do you think of it?

[Allan:] We (the field) still work on the same fundamental problems, but the field has diversified a lot. There are some things we don't do any more, such as some work on formal languages, but there are also many new exciting directions. You know for example, all the work on social networks, and links with economics. It is much, much more diverse field.

[Claire:] How about your own work?

[Allan:] I have moved away from complexity theory. It's become too difficult. For example, consider the algebraic geometry agenda to resolve the P versus NP question. I currently prefer to focus on developing a bettter understanding of conceptually simple combinatorial algorithms such as greedy algorithms, local search, dynamic programming.
For example, in mechanism design, if you design an algorithm that people cannot understand, then they're simply not going to use it.

[Claire:] Is there some recent progress that particularly interested you?

[Allan:] In terms of understanding simple algorithms, in the last SODA conference there was a paper by Poloczek and Schnitger giving a simple 3/4 algorithm for Max Sat, using randomization. In the upcoming ESA 2011 conference Poloczek proves in some strong sense that the algorithm cannot be de-randomized. But this is just the most recent result I am thinking of. The field has been continuously vibrant with great impact (e.g. complexity based cryptography).