Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 14

The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.

How Fast Do Algorithms Improve? [Point of View]

Sherry, Yash, Thompson, Neil C.·2021·Proceedings of the IEEE
DOI 10.1109/jproc.2021.3107219
Open this paper in CoChat — free account

Abstract

Algorithms determine which calculations computers use to solve problems and are one of the central pillars of computer science. As algorithms improve, they enable scientists to tackle larger problems and explore new domains and new scientific techniques[1],[2]. Bold claims have been made about the pace of algorithmic progress. For example, the President’s Council of Advisors on Science and Technology (PCAST), a body of senior scientists that advise the U.S. President, wrote in 2010 that “in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed”[3]. However, this conclusion was supported based on data from progress in linear solvers[4], which is just a single example. With no guarantee that linear solvers are representative of algorithms in general, it is unclear how broadly conclusions, such as PCAST’s, should be interpreted. Is progress faster in most algorithms? Just some? How much on average?

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/jproc.2021.3107219

Cites

13 of 13 references verified0 citation errors · 0 not checkable

Statistics

Figures

Image 1
CC-BY · From the PDF
Fig. 1 Algorithm discovery and improvement. (a) Number of new algorithm families discovered each decade. (b) Share of known algorithm families improved each decade. (c) Asymptotic time complexity class of algorithm families at first discovery. (d) Average yearly probability that an algorithm in one time complexity class transitions to another (average family complexity improvement). In (c) and (d) ' > n 3 ' includes time complexities that are superpolynomial but subexponential.
Fig. 1 Algorithm discovery and improvement. (a) Number of new algorithm families discovered each decade. (b) Share of known algorithm families improved each decade. (c) Asymptotic time complexity class of algorithm families at first discovery. (d) Average yearly probability that an algorithm in one time complexity class transitions to another (average family complexity improvement). In (c) and (d) ' > n 3 ' includes time complexities that are superpolynomial but subexponential.CC-BY · From the PDF
Fig. 2 Relative performance improvement for algorithm families, as calculated using changes in asymptotic time complexity. The comparison line is the SPECInt benchmark performance [20]. (a) Historical improvements for four algorithm families compared with the first algorithm in that family (n = 1 million). (b) Sensitivity of algorithm improvement measures to input size (n) for the 'nearest-neighbor search' algorithm family. To ease comparison of improvement rates over time, in (b) we align the starting periods for the algorithm family and the hardware benchmark.
Fig. 2 Relative performance improvement for algorithm families, as calculated using changes in asymptotic time complexity. The comparison line is the SPECInt benchmark performance [20]. (a) Historical improvements for four algorithm families compared with the first algorithm in that family (n = 1 million). (b) Sensitivity of algorithm improvement measures to input size (n) for the 'nearest-neighbor search' algorithm family. To ease comparison of improvement rates over time, in (b) we align the starting periods for the algorithm family and the hardware benchmark.CC-BY · From the PDF
Fig. 3 Distribution of average yearly improvement rates for 110 algorithm families, as calculated based on asymptotic time complexity, for problems of size: (a) n = 1 thousand, (b) n = 1 million, and (c) n = 1 billion. The hardware improvement line shows the average yearly growth rate in SPECInt benchmark performance from 1978 to 2017, as assembled by Hennessy and Patterson [20].
Fig. 3 Distribution of average yearly improvement rates for 110 algorithm families, as calculated based on asymptotic time complexity, for problems of size: (a) n = 1 thousand, (b) n = 1 million, and (c) n = 1 billion. The hardware improvement line shows the average yearly growth rate in SPECInt benchmark performance from 1978 to 2017, as assembled by Hennessy and Patterson [20].CC-BY · From the PDF
Fig. 4 Evaluation of the importance of leading constants in algorithm performance improvement. Two measures of the performance improvement for algorithm families (first versus last algorithm in each family) for n = 1 million. Algorithmic steps include leading constants in the analysis, whereas asymptotic performance drops them.
Fig. 4 Evaluation of the importance of leading constants in algorithm performance improvement. Two measures of the performance improvement for algorithm families (first versus last algorithm in each family) for n = 1 million. Algorithmic steps include leading constants in the analysis, whereas asymptotic performance drops them.CC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 8

  1. thompson, 2020, The computation limits of deep learning, arXiv 2007 05558
  2. manohara, 2018, Netflix Optimized Encodes
  3. ismail, 0, Why Algorithms Are the Future of Business Success
  4. bentley, 2006, Programming Pearls
  5. holdren, 2010, President Council of Advisors on Science and Technology
  6. 0, Division of Physics Computational and Data-Enabled Science and Engineering (CDS&E)—National Science Foundation
  7. 0, Division of Computing and Communication Foundations CCF Algorithmic Foundations (AF)—National Science Foundation
  8. 2018, TopUniversities QS World Rankings

Cited by

See all 14

Metadata

Authors
Sherry, Y., & Thompson, N. C.
ORCID
Thompson, Neil C.
Venue
Proceedings of the IEEE
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2021-11
Volume
109
Issue
11
Pages
1768-1777
ISSN
  • 0018-9219
  • 1558-2256
DOI
10.1109/jproc.2021.3107219
Cited by
14
References
13
Licence

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.