A Metastudy of Algorithm Lower Bounds
Algorithms are essential to the field of computer science, and algorithm designers are always searching for the mathematically optimal algorithms. Sherry and Thompson found that improvements to algorithm upper bounds have been steadily decreasing since the 1970s. In this work we aim to discover whet...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/140013 |
| _version_ | 1826199590401998848 |
|---|---|
| author | Liu, Emily |
| author2 | Thompson, Neil |
| author_facet | Thompson, Neil Liu, Emily |
| author_sort | Liu, Emily |
| collection | MIT |
| description | Algorithms are essential to the field of computer science, and algorithm designers are always searching for the mathematically optimal algorithms. Sherry and Thompson found that improvements to algorithm upper bounds have been steadily decreasing since the 1970s. In this work we aim to discover whether this could be because researchers have already found the optimal versions of many algorithms. In order to get a better sense of the picture, we compiled lower bounds on the algorithm families studied by Sherry and Thompson. We find that, while a few problems still have large gaps between upper and lower bounds where improvement is possible, over threequarters of these problems are already very close to being optimal! The “slowing progress” may in fact prove to be a triumph in disguise, as it is an indicator that many problems have achieved optimal solutions. |
| first_indexed | 2024-09-23T11:22:21Z |
| format | Thesis |
| id | mit-1721.1/140013 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:22:21Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1400132022-02-08T03:43:40Z A Metastudy of Algorithm Lower Bounds Liu, Emily Thompson, Neil Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Algorithms are essential to the field of computer science, and algorithm designers are always searching for the mathematically optimal algorithms. Sherry and Thompson found that improvements to algorithm upper bounds have been steadily decreasing since the 1970s. In this work we aim to discover whether this could be because researchers have already found the optimal versions of many algorithms. In order to get a better sense of the picture, we compiled lower bounds on the algorithm families studied by Sherry and Thompson. We find that, while a few problems still have large gaps between upper and lower bounds where improvement is possible, over threequarters of these problems are already very close to being optimal! The “slowing progress” may in fact prove to be a triumph in disguise, as it is an indicator that many problems have achieved optimal solutions. M.Eng. 2022-02-07T15:18:54Z 2022-02-07T15:18:54Z 2021-09 2021-11-03T19:25:43.065Z Thesis https://hdl.handle.net/1721.1/140013 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Liu, Emily A Metastudy of Algorithm Lower Bounds |
| title | A Metastudy of Algorithm Lower Bounds |
| title_full | A Metastudy of Algorithm Lower Bounds |
| title_fullStr | A Metastudy of Algorithm Lower Bounds |
| title_full_unstemmed | A Metastudy of Algorithm Lower Bounds |
| title_short | A Metastudy of Algorithm Lower Bounds |
| title_sort | metastudy of algorithm lower bounds |
| url | https://hdl.handle.net/1721.1/140013 |
| work_keys_str_mv | AT liuemily ametastudyofalgorithmlowerbounds AT liuemily metastudyofalgorithmlowerbounds |