Dipartimento di Informatica

Date: Thu 17 March 2022 at 14:00
Venue: Aula G50 - Edificio G, Viale Regina Elena
Speaker: Prof. Lorenzo Orecchia

Title: Fast Diffusion-based Algorithms for Vertex-based and Hypergraph Partitioning

Abstract:
Classical spectral graph theory is centered around the study of the quadratic forms of the graph Laplacian operator, through its structural relation to isoperimetric properties of the graph and his algorithmic connection with the heat diffusion process over the graph. In this talk, I will describe a generalization of this theory that focuses instead on bilinear forms of incidence operators and allows for more general structural results and novel algorithmic primitives. In particular, I will showcase a simple, efficiently computable nonlinear analogue of the heat diffusion process that allows us to detect sparse vertex-based separators and hypergraph separators. I will also describe its connection to the fastest-mixing markov chain over an unweighted undirected graph. This is joint work with Antares Chen and Erasmo Tani.

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.