Home > Ateneo > Dipartimenti, strutture e uffici > Centri > Centri Interateneo > European Centre for Living Technology > Events & news > Seminars > Revealing Structure in Large Graphs:Szemerédi's Regularity Lemma and Its Use in Pattern Recognition

Sommario

Revealing Structure in Large Graphs:Szemerédi's Regularity Lemma and Its Use in Pattern Recognition

27/05/2015

Date: 29th May 2015
Time: 2:30 pm
Venue: European Centre for Living Technology - San Marco 2940

Abstract:

Introduced in the mid-1970's as an intermediate step in proving a long-standing conjecture on arithmetic progressions, Szemeredi's regularity lemma has emerged over time as a fundamental tool in different branches of discrete mathematics and theoretical computer science. Roughly, it states that every graph can be approximated by the union of a small number of random-like bipartite graphs called regular pairs. In other words, the result provides us a way to obtain a good description of a large graph using a small amount of data, and can be regarded as a manifestation of the all-pervading dichotomy between structure and randomness. In this talk, I will provide an overview of the regularity lemma and variations thereof and will discuss its relevance in the context of structural pattern recognition.

Speaker:

Marcello Pelillo, DAIS/ECLT
Università Ca' Foscari Venezia

Bio sketch

Marcello Pelillo ​is a Full Professor of Computer Science at Ca' Foscari University of Venice, Italy, where he directs the European Center for Living Technology (ECLT). He is Fellow of the IEEE and of the IAPR.


 

© Ca'Foscari 2017

Ultima modifica: 27/05/2015 da ECLT