Wednesday, May 21, 2014

What's Important in Algoirthms

I saw this interesting article up on 20 questions with Don Knuth, worth reading just for the fun of it.  But the following question on work in algorithm design and analysis particularly interested me, and I nodded especially hard resonating with the statement:

Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published.
 
But here's the whole question/answer for context.

15. Robert Tarjan, Princeton: What do you see as the most promising directions for future work in algorithm design and analysis? What interesting and important open problems do you see?
Don Knuth: My current draft about satisfiability already mentions 25 research problems, most of which are not yet well known to the theory community. Hence many of them might well be answered before Volume 4B is ready. Open problems pop up everywhere and often. But your question is, of course, really intended to be much more general.
In general I'm looking for more focus on algorithms that work fast with respect to problems whose size, n, is feasible. Most of today's literature is devoted to algorithms that are asymptotically great, but they are helpful only when n exceeds the size of the universe.
In one sense such literature makes my life easier, because I don't have to discuss those methods in TAOCP. I'm emphatically not against pure research, which significantly sharpens our abilities to deal with practical problems and which is interesting in its own right. So I sometimes play asymptotic games. But I sure wouldn't mind seeing a lot more algorithms that I could also use.
For instance, I've been reading about algorithms that decide whether or not a given graph G belongs to a certain class. Is G, say, chordal? You and others discovered some great algorithms for the chordality and minimum fillin problems, early on, and an enormous number of extremely ingenious procedures have subsequently been developed for characterizing the graphs of other classes. But I've been surprised to discover that very few of these newer algorithms have actually been implemented. They exist only on paper, and often with details only sketched.
Two years ago I needed an algorithm to decide whether G is a so-called comparability graph, and was disappointed by what had been published. I believe that all of the supposedly "most efficient" algorithms for that problem are too complicated to be trustworthy, even if I had a year to implement one of them.
Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published.
Another issue, when we come down to earth, is the efficiency of algorithms on real computers. As part of the Stanford GraphBase project I implemented four algorithms to compute minimum spanning trees of graphs, one of which was the very pretty method that you developed with Cheriton and Karp. Although I was expecting your method to be the winner, because it examines much of the data only half as often as the others, it actually came out two to three times worse than Kruskal's venerable method. Part of the reason was poor cache interaction, but the main cause was a large constant factor hidden by O notation.

8 comments:

Anonymous said...

I think that both theory and practical algorithms should be encouraged, for different reasons. The main problem is in the middle: a new algorithm that is simpler that all already-published algorithms but not at the level of being implementable faces several problems when trying to publish it.

Mark Wilson said...

Thanks for the link to the Knuth Q&A - some very interesting material there. The topic of the missing implementations of published algorithms has been discussed before (on this blog I think).

It seems to me that this is the theoretical CS version of the non-reproducibility crisis currently occurring in disciplines such as psychology.

Have you seen any progress over the last 5 years?

Maybe giving DOIs for code will allow people to get citation credit and go some way to improving the situation. It seems that the reward system of scholarship is badly broken, when obscure "improvements" of algorithms that could never be implemented get points, but careful comparison of actual running times of useful implementations of more important algorithms does not. Math envy is a major problem in many disciplines!

Unknown said...

this is a great high voted question on that "powerful algorithms too complex to implement" & rjlipton has a great blog on the subject also re "galactic algorithms". gotta blog on this sometime & include your blog!

Anonymous said...

It's important to tell that 'Algoirthms' is incorrect.

Anonymous said...

Math envy or not, progress on fundamental and difficult problems in algorithms and theoretical computer science is not going to happen by carefully implementing existing algorithms. Pragmatic considerations are of course important but academic TCS has to advance the frontiers.

Michael Mitzenmacher said...

Anon #5: I think I disagree with pretty much everything in your comment. Since that's rare, I'll respond.

"...progress on fundamental and difficult problems in algorithms and theoretical computer science is not going to happen by carefully implementing existing algorithms"

I just don't think this is correct. Often implementing existing algorithms is what gives you insight allowing for improvements -- including significant theoretical improvements. I could spout examples from myself and students, but I'm sure you can find some of your own. The relationship between theory and practice is a 2-way street. Sure, implementation isn't the ONLY way to make progress, but it's also a way that should not be ignored.

"Pragmatic considerations are of course important but academic TCS has to advance the frontiers."

In specifically algorithms, advancing the frontiers should definitely include "pragmatic considerations". "Use" has always been at least a criteria for successful algorithmic work, making pragmatic considerations important.

Anonymous said...

"Pragmatic considerations are of course important but academic TCS has to advance the frontiers."

how did TCS get to this point...

Michael Mitzenmacher said...

Anonymous X: I was talking about Algoirthms. What are Algorithms? (Just kidding.)

Anonymous June 1: I'm not surprised by the "pragmatic" comment. I think TCS should have room for a wide spectrum of researchers, certainly including those that aren't interested in practical implications at all. The "T" is for "Theoretical". But I think I'm on record as noting that TCS has, culturally, tilted pretty far in the "non-practical" direction, so that a comment like Anon May 26 is both unsurprising and, perhaps to many, uncontroversial.