"Ramanujan graphs: Theory and Applications"

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:


- Meeting id: 931 7595 9328
- Password: 756022

Short Bio:

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.


"Ramanujan graphs: Theory and Applications"




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.


Também lhe pode interessar


"Hyperparameter Importance for Image Classification by Residual Neural Networks"

Prof. Jan N. van Rijn dá palestra no DCC


"Sustainability factors in telemedicine services for rural communities in low-income regions"

Prof. Ignacio Egido dá palestra no DCC


"Randomness Beacons for Enhanced Public Auditability"

René Peralta and Luís Brandão dão palestra no DCC