|
Speaker: Josh Alman Columbia University Wednesday, September 18, 2024 11:30 am: Lunch (Kitchen) Location: Yale Institute for Foundations of Data Science & Webcast, 219 Prospect Street, New Haven, CT 06511 |
Add To: Google Calendar | Outlook | iCal File
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/
