Lecture

Building Ramanujan Graphs

Description

This lecture discusses the challenges of using the probabilistic method to construct Ramanujan graphs and proposes a solution involving polynomials. The instructor explains the concept of expander graphs and their role in solving NP-hard problems. The lecture covers topics such as belief negotiation, continuous and discrete distances, and the properties of Ramanujan graphs. It also delves into the interplay between eigenvalues and eigenvectors of matrices, emphasizing the importance of tracking all eigenvalues. The presentation concludes with a detailed analysis of interlacing properties and characteristic polynomials, showcasing their significance in graph theory and linear algebra.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.