Expander Graphs Courses and Certifications

Ryan O'Donnell

Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit

Explore derandomization techniques using expander graphs to reduce error in randomized algorithms without significantly increasing random bits used.

• YouTube
• 23 minutes
• On-Demand
• Free Video

Institute for Advanced Study

Sparse Matrices in Sparse Analysis - Anna Gilbert

Explore sparse matrices in compressive sensing, focusing on expander graphs and their applications. Learn about metric repair scenarios and algorithms for sparse signal recovery.

• YouTube
• 1 hour 2 minutes
• On-Demand
• Free Video

USENIX

DistCache - Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching

Innovative distributed caching mechanism providing provable load balancing for large-scale storage systems. Partitions hot objects and adaptively routes queries, enabling linear cache throughput increase with node count.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

USENIX

Understanding Lifecycle Management Complexity of Datacenter Topologies

Explores lifecycle management complexity of datacenter topologies, comparing Clos and expander graphs. Introduces FatClique, a new topology combining wiring simplicity and expandability, with insights on deployment and expansion costs.

• YouTube
• 22 minutes
• On-Demand
• Conference Talk

USENIX

Expanding Across Time to Deliver Bandwidth Efficiency and Low Latency

Innovative network design for datacenters combining low-latency delivery and high-bandwidth efficiency through dynamic reconfiguration, outperforming static topologies for various workloads.

• YouTube
• 22 minutes
• On-Demand
• Conference Talk

Ryan O'Donnell

Dinur's PCP- Degree-Reduction, Expanderizing, Mini-PCP - Lecture 27c of CS Theory Toolkit

Explore Dinur's PCP Theorem proof, covering degree-reduction, expanderizing, and alphabet-reduction in theoretical computer science. Gain insights into advanced concepts for research in computational complexity.

• YouTube
• 26 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

High Dimensional Expanders

Explore high-dimensional expanders, their mathematical properties, and applications in theoretical computer science. Learn about coboundary and spectral expansion, and their implications for complex structures.

• YouTube
• 1 hour 15 minutes
• On-Demand
• Free Video

IEEE

Expander Graphs - Both Local and Global

Explore expander graphs, their local and global properties, construction methods, and applications in this concise IEEE talk by experts in the field.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

International Centre for Theoretical Sciences

Non-virtually Abelian Discontinuous Group Actions vs Proper SL(2,R)-Actions - Aleksy Tralle

Explore non-virtually Abelian discontinuous group actions and proper SL(2,R)-actions in this advanced mathematics lecture, part of a program on Zariski dense subgroups and geometric applications.

• YouTube
• 47 minutes
• On-Demand
• Free Video

Simons Institute

List Decoding of Tanner and Expander Amplified Codes

Explore advanced error-correcting code techniques, focusing on list decoding for Tanner and expander amplified codes, with insights from Shashank Srivastava's research.

• YouTube
• 48 minutes
• On-Demand
• Free Video

USENIX

Flattened Clos - Designing High-performance Deadlock-free Expander Data Center Networks Using Graph Contraction

Innovative approach to designing high-performance, deadlock-free expander data center networks using graph contraction, offering improved efficiency and throughput compared to traditional Clos networks.

• YouTube
• 17 minutes
• On-Demand
• Conference Talk

Simons Institute

Sublinear Time Algorithms for Max-Cut Approximation on Expander Graphs

Explore random walks on graphs to achieve better-than-1/2 approximation for max-cut on expanding and clusterable graphs, using sublinear time algorithms.

• YouTube
• 32 minutes
• On-Demand
• Free Video

Simons Institute

Recent Developments in Testing Bounded-Degree Graphs

Explore recent advancements in testing bounded-degree graphs, including locally-characterized expander graphs, graph isomorphism studies, and applications of robustly self-ordered graphs.

• YouTube
• 46 minutes
• On-Demand
• Free Video

BIMSA

Hamiltonicity of Expanders: Optimal Bounds and Applications

Explore optimal bounds and applications of Hamiltonicity in expanders with Nemanja Draganić, delving into extremal and probabilistic combinatorics, Ramsey theory, and theoretical computer science.

• YouTube
• 1 hour 2 minutes
• On-Demand
• Free Video

Institute for Advanced Study

Analytic Insights into the Zig-Zag Product and Its Friends - Part II

Explore advanced analysis of graph operators using full spectrum and analytic techniques. Gain insights into Zig-Zag product, derandomized squaring, and their optimal bounds through finite free probability and analytic combinatorics.

• YouTube
• 2 hours 6 minutes
• On-Demand
• Free Video