Expanders and Extractors

# click the upper-left icon to select videos from the playlist

source: Simons Institute     2017年1月30日
These presentations were supported in part by an award from the Simons Foundation.
This workshop will focus on explicit constructions of graphs and functions with pseudorandom properties. There will be two main themes related to each object in the title. For expanders, these will be proofs of existence of expander graphs using lifts, a la Bilu-Linial and Marcus-Spielman-Srivastava, and the possibility of using the method to obtain explicit constructions of Ramanujan expanders of all degrees; and constructions of Cayley expanders and the group-theoretic results motivated by such results. For randomness extractors, these will be constructions of extractors for independent sources and their applications to the construction of Ramsey graphs and other objects; and constructions of extractors in other settings and their applications to pseudorandom generators, coding theory, cryptography and other areas of computer science.
For more information, please visit ttps://simons.berkeley.edu/workshops/pseudorandomness2017-1

Explicit Constructions of Two-Source Extractors and Ramsey Graphs Eshan Chattopadhyay, Institute for Advanced Study https://simons.berkeley.edu/talks/esh... 42:27
Correlation Breakers, Independence-Preserving Mergers, and their Applications 45:45
An Efficient Reduction from Non-Malleable Extractors to Two-Source Extractors, and... 45:40
Extractors for Algebraic Sources 47:24
Ramanujan Covers 48:14
Two Existence Proofs of Ramanujan Graphs 41:59
Some of My Favorite Open Problems on Expanders and Extractors 46:26
High Dimensional Expanders and PCPs 50:04
Discrete Log Problem with Respect to the LPS generators on PGL_2  47:15
Golden Gates, Ramanujan Complexes and Ramanujan Digraphs 45:47
Super-Approximation 46:16
High Dimensional Expanders 50:59
Random Walks on Ramanujan Graphs, Digraphs and Complexes 56:53
A Generalized Alon-Boppana Bound and Weak Ramanujan Graphs 47:40
Word-Measures on Unitary Groups 49:40
What are High-Dimensional Expanders? 46:39
Pseudorandomness When the Odds Are Against You 46:21
Finding and Using Expanders in Locally Sparse Graphs and in Sparse Random Graphs 48:44
Spectral Gaps and Geometric Representations 43:52
Improved Deterministic Randomness Extraction from Non-Binary Santha-Vazirani Sources 41:59
The Diameter of the Symmetric Group: Ideas and Tools 36:11