Events
FDS Colloquium
FDS Colloquium: Josh Alman (Columbia), “Algorithms and Hardness for Kernel Density Estimation and Attention”
 |
Speaker: Josh Alman Columbia University Wednesday, September 18, 2024 11:30AM - 1:00PM 11:30 am: Lunch (Kitchen)
12:00 pm: Talk (Seminar Room #1327)
|
Webcast Link (via Zoom – starts at 12:00): https://yale.zoom.us/s/7859884026
“Algorithms and Hardness for Kernel Density Estimation and Attention”
Abstract: This talk will focus on two related computational problems. The first is Kernel Density Estimation, a statistical task which has diverse applications from machine learning to computational physics. The second is Attention, the task at the core of Transformer and other Large Language Models.
Both of these problems have straightforward quadratic-time algorithms, and I’ll discuss a recent line of work investigating when faster algorithms are possible. I’ll survey two algorithmic techniques which lead to almost linear-time algorithms in different parameter regimes: the Fast Multipole Method, and the polynomial method. I’ll then overview our new fine-grained hardness results, which prove that these techniques are essentially optimal in the parameter regimes where they apply, and highlight the situations where improvements may be possible.
Based on joint work with Amol Aggarwal (in CCC 2022), Zhao Song (in NeurIPS 2023), and Yunfeng Guan (in CCC 2024).
Bio: Josh Alman is an Assistant Professor of Computer Science at Columbia University. He is a theoretical computer scientist who works on algorithm design and complexity theory, focusing especially on algebraic tools for speeding up algorithms.
Website: joshalman.com/
Add To: Google Calendar | Outlook | iCal File
Submit an Event
Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.