That's pedantic and also incorrect. The problem of whether an exact solution can be found efficiently can be put to rest. You might not choose to use this algorithm, but that's not really the point of algorithms research. You've just picked a strawman to criticise the wording on.
I don't think so. I think he is pointing out a really, really important thing that many overlook because of the way we have come to teach computer science.
When evaluating different algorithms, there are lots of criteria we could use. How often is it correct? How long does it take to run? How difficult is it for people to read? How often does it use the letter "r" which happens to be broken on my keyboard?
Computer science made ENORMOUS strides by picking out a specific criterion (running time on the computers of the time) and finding a way to make it mathematically rigorous (asymptotic performance analysis, Big-O notation, and all of the related mechanisms that we learn in computer science classes). This was TREMENDOUSLY valuable, and by turning the whole power of mathematical analysis loose on the problem it formed the modern field of algorithm analysis and completely transformed how we build computers.
But we need to remember that this is base on one particular simplification of how computers work. It assumes a Von-neuman architecture where execution steps are the key criterion. We have extended this framework to consider things like parallel execution... that was fruitful also. More recently, we've been noticing that our actual machines are no longer dominated by the "steps" in the algorithm, but most often are dominated by memory usage, so we have turned the same formalism onto the use of memory -- but still (in my opinion) lack a rigorous approach for analyzing the combination of steps taken and memory usage.
Even more significant is the fact that there are OTHER things we could trade off. One of those is accuracy. Look at some of the research on probabilistic algorithms: you will find that there are some incredible gains to be made with losses in accuracy that are well within the bounds of what are acceptable for most uses. Yet this isn't covered in an introductory computer science course, so many programmers are not even aware of the option. With so much of traditional algorithm analysis already mapped out by the past several decades of researchers, much of the fertile ground in the near future will, I believe, lie in investigating these other sorts of tradeoffs.
No - there are many fruitful formalisations of parallel programming (the CLRS chapter is pretty good) and indeed, of non-von Neumann architectures (check out balancing, comparison networks etc etc).
This sort of work is not reliant on von-Neumann - it quantifies the amount of work you need to do. Coincidentally, the algorithm listed parallelises very well; it has a good span.
Of course it is useful to avoid galactic algorithms, but the article is totally correct. It would be incorrect to read its conclusion as anything but what it actually says. As a general principle, sure, but it shouldn't be a criticism of this article.
There are 2 much better criticism they could have made:
1. The proof is conditional on the unproven hypothesis that 3-SAT requires 2^n time.
2. There could be an exact algorithm which uses randomness and has less than n^2 expected runtime. After all, it's still unknown whether ZPP=EXP afaik (although it almost certainly does not).
There is plenty of work being done on approximation algorithms, for good reason. If you're dealing with scientific data that's subject to measurement noise, it's valuable to research whether that 0.1% difference actually matters or not. That said, this is great work, it's just not a closed case.
Yes, of course - and there are some really cool proofs (easy to understand also). A personal favourite is the Run of Christofides. BUT that's not relevant here.
It seems relevant to start talking about approximation algorithms as the next step after proving a "1000 year" runtime for exactly comparing genomes. My understanding is that comp bio folks typically use heuristics anyway.
