An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo
Computer Science/Discrete Mathematics Seminar II
Topic: An Introduction to Lifted Expander Graphs
Speaker: Fernando Granha Jeronimo
Affiliation: Member, School of Mathematics
Date: December 14, 2021
Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to start from a small expander and apply (once or several times) a well-known lifting operation to obtain a larger expander. In this talk, we will describe an explicit (near-Ramanujan) construction of lifted expander graphs possessing an additional large symmetry structure. The analysis boils down to a more careful counting argument building on the incredible progress seen in this kind of construction. The additional symmetry structure of our lifted expanders has applications to coding theory.
This is based on joint work with Tushant Mittal, Ryan O'Donnell, Pedro Paredes and Madhur Tulsiani.
Видео An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo канала Institute for Advanced Study
Topic: An Introduction to Lifted Expander Graphs
Speaker: Fernando Granha Jeronimo
Affiliation: Member, School of Mathematics
Date: December 14, 2021
Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to start from a small expander and apply (once or several times) a well-known lifting operation to obtain a larger expander. In this talk, we will describe an explicit (near-Ramanujan) construction of lifted expander graphs possessing an additional large symmetry structure. The analysis boils down to a more careful counting argument building on the incredible progress seen in this kind of construction. The additional symmetry structure of our lifted expanders has applications to coding theory.
This is based on joint work with Tushant Mittal, Ryan O'Donnell, Pedro Paredes and Madhur Tulsiani.
Видео An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo канала Institute for Advanced Study
Показать
Комментарии отсутствуют
Информация о видео
15 декабря 2021 г. 0:57:41
01:55:12
Другие видео канала
Classical Turbulence as Quantum Geometry - Alexander Migdal
Scholar Spotlight: Anna Bokov
Proof complexity - an introduction - Avi Wigderson
Stability for functional and geometric inequalities - Robin Neumayer
Modular bootstrap, Segal's axioms and resolution of Liouville conformal field theory -Rhodes, Vargas
Book Trailer for "The Usefulness of Useless Knowledge"
Progress on Celestial Holography - Andrew Strominger
Non-perturbative Studies of JT Gravity and Supergravity using Minimal Strings - Clifford V. Johnson
Epsilon regularity and removable singularities - Karen Uhlenbeck
Direct and dual Information Bottleneck frameworks for Deep Learning - Tali Tishby
Entanglement Wedge Reconstruction in Infinite-Dimensional Hilbert Spaces - Monica Jinwoo Kang
Free Energy from Replica Wormholes - Netta Engelhardt
The challenges of model-based reinforcement learning and how to overcome them - Csaba Szepesvári
Sparse matrices in sparse analysis - Anna Gilbert
Dynamics of Deep Neural Networks--A Fourier Analysis Perspective-Yaoyu Zhang
Emergent linguistic structure in deep contextual neural word representations - Chris Manning
On the critic function of implicit generative models - Arthur Gretton
Introduction to Interpretable Machine Learning II - Cynthia Rudin
The nonlinear stability of the Schwarzschild metric without symmetry - Mihalis Dafermos
Bourgain Remembrance - Various Speakers