No próximo dia 24 de Julho, pelas 17h00, o Pedro Paredes, alumnus do DCC, irá dar uma palestra intitulada "Ramanujan graphs: Theory and Applications".
A palestra é organizada pelo DCC-FCUP e pelo grupo de investigação CRACS-INESC TEC e é aberta a todos os interessados.
A sessão será de forma remota, utilizando os seguintes dados:
Pedro Paredes is a PhD student at Carnegie Mellon University, advised by Professor Ryan O'Donnell. He did his Undergraduate and Master's in Computer Science at the Faculty of Sciences of the University of Porto. His work focuses on the theory of computation and his research interests are mainly random matrix theory, pseudorandomness, complexity theory and combinatorics.
Title
"Ramanujan graphs: Theory and Applications"
Abtract
Expanders graphs are simultaneously sparse and highly connected, such that every small set of vertices has many edges on its boundary. The study of these combinatorial objects has a long history, dating back to the early 70s. These have found a rich number of applications, ranging different contexts. In the theory of computation, they are surprisingly useful in constructing error correcting codes and in pseudorandomness problems. In mathematics, they play a role in the study of metric embeddings. Among the many other interesting applications, we also find some more practical ones, like in the design and analysis of communication networks.
Ramanujan graphs are, in some sense, perfect expander graphs. We are going to look at the definition of Ramanujan graphs, describe what goes into constructing them, and also see how they can be used in some of the above applications. In the process, we will briefly go through the different developments in the field, culminating in a recent work of ours that describes an efficient construction of nearly optimal Ramanujan graphs.