Explicit Near-Fully X-Ramanujan Graphs
Offered By: IEEE via YouTube
Course Description
Overview
Explore the concept of explicit near-fully X-Ramanujan graphs in this 22-minute IEEE conference talk by Ryan O'Donnell and Xinyu Wu from Carnegie Mellon University. Delve into the fascinating world of finite graphs that resemble infinite graphs, and discover how random finite graphs can exhibit similar properties. Examine the concept of d-regular trees and learn about graphs that spectrally resemble infinite structures. Investigate the role of adjacency matrices and formal polynomials in graph theory. Gain insights into the approach using finite permutations and matrix-weighted polynomials. Conclude with a discussion of the presenters' results and potential open problems in this field of study.
Syllabus
Intro
Ramanujan graphs: Finite graphs which resemble infinite graphs
Random finite graphs which resemble infinite graphs
Beyond d-regular trees
Spectrally resembling infinite graphs
Adjacency matrix
Consider the formal polynomial
Approach: finite permutations
Matrix-weighted polynomials
Our results
Open problems
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Graph Partitioning and ExpandersStanford University via NovoEd Spectral Aspects of Symmetric Matrix Signings
Simons Institute via YouTube Theory Seminar - Algorithms and Hardness for Linear Algebra on Geometric Graphs, Aaron Schild
Paul G. Allen School via YouTube Spectral Graph Theory - Eigenvalues at CMU - Lecture 15a of CS Theory Toolkit
Ryan O'Donnell via YouTube Spectral Graph Theory - Minimizing/Maximizing the Quadratic Form
Ryan O'Donnell via YouTube