Events
Colloquium
Heat Diffusions as Regularized Eigenvectors for Fast Balanced Partitioning
 |
Speaker: Lorenzo Orecchia Assistant Professor of Computer Science University of Chicago Thursday, March 5, 2026 11:30AM - 5:00PM Lunch with the speaker in KT1307 11:30am-12:30pm
Talk in 1327 from 4:00-5:00pm Location: Yale Institute for Foundations of Data Science Common Area, Kline Tower 13th Floor, New Haven, CT 06511 and via Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=c63a1846-e7bb-45c6-a995-b40300fd6a34 |
Abstract: We give a novel, simpler spectral algorithm for the problem of approximating the minimum conductance $b$-balanced cut in an undirected weighted graph. Our method is a simple modification of the recursive eigenvector algorithm, where eigenvector computations are replaced heat diffusions, which act as regularized analogues of the eigenvector. Finally, the algorithm outputs a new kind of certificate for the absence of a balanced cut, which leads to a number of open questions.
Speaker Bio: Lorenzo Orecchia is an assistant professor in the Department of Computer Science at the University of Chicago. Lorenzo’s research focuses on the design of efficient algorithms for fundamental computational challenges in machine learning and combinatorial optimization. His approach is based on combining ideas from continuous and discrete optimization into a single framework for algorithm design. Lorenzo obtained his PhD in computer science at UC Berkeley under the supervision of Satish Rao in 2011, and was an applied mathematics instructor at MIT under the supervision of Jon Kelner until 2014. He was a recipient of the 2014 SODA Best Paper award and a co-organizer of the Simons semester “Bridging Continuous and Discrete Optimization” in Fall 2017.
Add To: Google Calendar | Outlook | iCal File
- Colloquium
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.