How fast are Algorithms Improving?


Julian Shun
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.

Neil Thompson 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.

Yash Sherry Bio: Yash Sherry is a Visiting Student/Research Assistant at the SuperTech Lab, MIT CSAIL. He works under the guidance of Dr. Thompson on Algorithm Wiki and Quantum algorithmic analysis. He is currently a CS graduate student at GeorgiaTech where he is specializing in Machine Learning. Prior to this, he has worked on research projects with Stanford and CMU. He has also been a part of Irisys Lab (Korea), Mozilla and Microsoft in different roles. Currently, he is working on a tech startup in Boston that provides software services to student startups.