How close are algorithms to being optimal?

Speaker: Neil Thompson , MIT CSAIL

Date: Wednesday, April 06, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Event Type: Seminar

Room Description: https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, jshun@mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: http://www.neil-t.com/about-me/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu, toc@csail.mit.edu

Reminder Subject: TALK: How close are algorithms to being optimal?

******************IMPORTANT NOTE ABOUT REGISTRATION******************
- The registration link for Spring 2022 is the same as the link from Fall 2021.
- Please save the Zoom link that you receive after you register. This link will stay the same for all subsequent Fast Code seminars.
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 3:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

Abstract: The search for better algorithms is one of the defining goals of computer science. In this article we measure progress in achieving this goal for a broad set of important problems. We find a hitherto unheralded triumph: most are already provably optimal. Of the 113 problems prioritized by algorithm textbook writers, 65% are asymptotically optimal, while the rest have gaps remaining between the best known algorithms and theoretical bounds: 14% have a sublinear gap, 7% have a linear gap, 13% have a polynomial gap, and 1% have an exponential gap. Our findings have important implications for future algorithmic progress, showing where there is still potential for improvement and where progress on solving problems exactly is exhausted and therefore other techniques (such as approximation) will be needed.

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.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

This event is not part of a series.

Created by Julian J. Shun at Friday, April 01, 2022 at 10:46 AM.