Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Explicit Near-Fully X-Ramanujan Graphs

IEEE via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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

Reviews

Start your review of Explicit Near-Fully X-Ramanujan Graphs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.