How fast are Algorithms Improving?

Abstract: Quantitative analyses of how fast algorithms are improving are usually done ad-hoc. Longer term analyses are quite rare - in fact, almost all use the single example of Linear Solvers. In this paper, we gather data on 127 different algorithm families from more than 40 textbooks and 1000 research papers to present the first comprehensive look at algorithm progress ever assembled. We find that as a whole algorithms have undergone substantial progress, but with huge variation: in some cases, progress rivals those from other important sources (e.g. Moore's Law for computer hardware), but in other cases it shows relatively little progress.

Bio: I am an Innovation Scholar at MIT's Computer Science and Artificial Intelligence Lab and the Initiative on the Digital Economy.

I am also an Associate Member of the Broad Institute. Previously, I was an Assistant Professor of Innovation and Strategy at the MIT Sloan School of Management, where I co-directed the Experimental Innovation Lab (X-Lab), and a Visiting Professor at the Laboratory for Innovation Science at Harvard. I have advised businesses and government on the future of Moore's Law and have been on National Academies panels on transformational technologies and scientific reliability.

I did my PhD in Business and Public Policy at Berkeley, where I also did Masters degrees in Computer Science and Statistics. I have a masters in Economics from the London School of Economics, and undergraduate degrees in Physics and International Development. Prior to academia, I worked at organizations such as Lawrence Livermore National Laboratories, Bain and Company, The United Nations, the World Bank, and the Canadian Parliament.