- How close are algorithms to...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2022
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
Created by Julian J. Shun at Friday, April 01, 2022 at 10:46 AM.