Segnalo la presenza di questo colloquio, che non fa parte della nostra serie di seminari ma ha un tema che potrebbe essere di interesse per gli iscritti alla lista.
È una "lectio magistralis" che fa parte delle celebrazioni per i 50 anni del corso di laurea in informatica. Si terrà nell'aula magna del polo Pontecorvo (edificio E) lunedì 18 novembre alle 15:30.
Cordialmente, -federico
-------- Forwarded Message -------- Subject: [Dipartimento.di] Lectio Luca Trevisan Date: Fri, 15 Nov 2019 09:55:55 +0100 From: Gian Luigi Ferrari gian-luigi.ferrari@unipi.it To: CDD cdd@di.unipi.it, dipartimento@di.unipi.it
Lo avevo comunicato in consiglio ma mi sono scordato di mandarlo via mail. Rimedio
Title: A Theory of Spectral Clustering Speaker: Luca Trevisan
Abstract: Spectral clustering algorithms find clusters in a given network by exploiting properties of the eigenvectors of matrices associated with the network. As a first step, one computes a spectral embedding, that is a mapping of nodes to points in a low-dimensional real space; then one uses geometric clustering algorithms such as k-means to cluster the points corresponding to the nodes.
Such algorithms work so well that, in certain applications unrelated to network analysis, such as image segmentation, it is useful to associate a network to the data, and then apply spectral clustering to the network. In addition to its application to clustering, spectral embeddings are a valuable tool for dimension-reduction and data visualization.
The performance of spectral clustering algorithms has been justified rigorously when applied to networks coming from certain probabilistic generative models.
A more recent development, which is the focus of this lecture, is a worst-case analysis of spectral clustering, showing that, for every graph that exhibits a certain cluster structure, such structure can be found by geometric algorithms applied to a spectral embedding.
Such results generalize the graph Cheeger’s inequality (a classical result in spectral graph theory), and they have additional applications in computational complexity theory and in pure mathematics.
———
Bio: Luca Trevisan is a professor of Computer Science at Bocconi University. Luca studied at the Sapienza University of Rome, he was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, moving back to Italy in 2019.
Luca's research is in theoretical computer science, and it is focused on computational complexity and graph algorithms.
Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians. He is a recipient of a 2019 ERC Advanced Grant.
______________________________________________ Dipartimento.di mailing list Dipartimento.di@listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di
Il colloquio di cui vi dicevo è rinviato a data da definirsi, vista la chiusura straordinaria dell'ateneo domani.
Cordialmente, -federico
On 15/11/2019 11.45, Federico Poloni wrote:
Segnalo la presenza di questo colloquio, che non fa parte della nostra serie di seminari ma ha un tema che potrebbe essere di interesse per gli iscritti alla lista.
È una "lectio magistralis" che fa parte delle celebrazioni per i 50 anni del corso di laurea in informatica. Si terrà nell'aula magna del polo Pontecorvo (edificio E) lunedì 18 novembre alle 15:30.
Cordialmente, -federico
-------- Forwarded Message -------- Subject: [Dipartimento.di] Lectio Luca Trevisan Date: Fri, 15 Nov 2019 09:55:55 +0100 From: Gian Luigi Ferrari gian-luigi.ferrari@unipi.it To: CDD cdd@di.unipi.it, dipartimento@di.unipi.it
Lo avevo comunicato in consiglio ma mi sono scordato di mandarlo via mail. Rimedio
Title: A Theory of Spectral Clustering Speaker: Luca Trevisan
Abstract: Spectral clustering algorithms find clusters in a given network by exploiting properties of the eigenvectors of matrices associated with the network. As a first step, one computes a spectral embedding, that is a mapping of nodes to points in a low-dimensional real space; then one uses geometric clustering algorithms such as k-means to cluster the points corresponding to the nodes.
Such algorithms work so well that, in certain applications unrelated to network analysis, such as image segmentation, it is useful to associate a network to the data, and then apply spectral clustering to the network. In addition to its application to clustering, spectral embeddings are a valuable tool for dimension-reduction and data visualization.
The performance of spectral clustering algorithms has been justified rigorously when applied to networks coming from certain probabilistic generative models.
A more recent development, which is the focus of this lecture, is a worst-case analysis of spectral clustering, showing that, for every graph that exhibits a certain cluster structure, such structure can be found by geometric algorithms applied to a spectral embedding.
Such results generalize the graph Cheeger’s inequality (a classical result in spectral graph theory), and they have additional applications in computational complexity theory and in pure mathematics.
———
Bio: Luca Trevisan is a professor of Computer Science at Bocconi University. Luca studied at the Sapienza University of Rome, he was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, moving back to Italy in 2019.
Luca's research is in theoretical computer science, and it is focused on computational complexity and graph algorithms.
Luca received the STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians. He is a recipient of a 2019 ERC Advanced Grant.
Dipartimento.di mailing list Dipartimento.di@listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/dipartimento.di _______________________________________________ Numpi.di mailing list Numpi.di@listgateway.unipi.it http://listgateway.unipi.it/mailman/listinfo/numpi.di
-
Federico Poloni