Algorithms are one of the fundamental building blocks of computing. But current evidence about how fast algorithms improve is anecdotal, using small numbers of case studies to extrapolate. In this work, we gather data from 57 textbooks and more than 1,137 research papers to present the first systematic view of algorithm progress ever assembled. There is enormous variation. Around half of all algorithm families experience little or no improvement. At the other extreme, 13% experience transformative improvements, radically changing how and where they can be used. Overall, we find that, for moderate-sized problems, 30% to 45% of algorithmic families had improvements comparable or greater than those that users experienced from Moore's Law and other hardware advances.
Joint work with Yash M. Sherry.
Bio: Dr. Neil Thompson is an Innovation Scholar at MIT's Computer Science and Artificial Intelligence Lab and the Initiative on the Digital Economy. He is also an Associate Member of the Broad Institute. Previously, he was an Assistant Professor of Innovation and Strategy at the MIT Sloan School of Management, where he co-directed the Experimental Innovation Lab (X-Lab), and a Visiting Professor at the Laboratory for Innovation Science at Harvard. He has advised businesses and government on the future of Moore's Law and have been on National Academies panels on transformational technologies and scientific reliability. He did his PhD in Business and Public Policy at Berkeley, where he also did Masters degrees in Computer Science and Statistics. He has a masters in Economics from the London School of Economics, and undergraduate degrees in Physics and International Development. Prior to academia, he worked at organizations such as Lawrence Livermore National Laboratories, Bain and Company, The United Nations, the World Bank, and the Canadian Parliament.