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

YouTube

Spectral Algorithms from Induced Subgraphs of Cayley Graphs

Institute for Advanced Study via YouTube

Overview

Explore a two-hour computer science seminar where Peter Manohar from the Institute for Advanced Study presents a novel methodology for solving algorithmic and combinatorial problems through spectral analysis of Cayley graphs. Learn about a two-step approach that involves reducing problems to bounding homogeneous degree-q multilinear polynomials and analyzing spectral properties of induced subgraphs known as "Kikuchi graphs." Discover practical applications including algorithms for solving semirandom constraint satisfaction problems, proving near-optimal extremal girth vs. density trade-offs for hypergraphs, improving lower bounds for q-query locally decodable codes, and establishing exponential lower bounds for 3-query locally correctable codes. Gain insights into advanced mathematical concepts at the intersection of discrete mathematics and computer science, presented in both in-person and remote formats.

Syllabus

am|Simonyi 101 and Remote Access

Taught by

Institute for Advanced Study

Reviews

Start your review of Spectral Algorithms from Induced Subgraphs of Cayley 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.