YoVDO

Explicit Near-Fully X-Ramanujan Graphs

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Combinatorics Courses Graph Theory Courses Spectral Graph Theory Courses

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 Expanders
Stanford 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