YoVDO

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

Offered By: Ryan O'Donnell via YouTube

Tags

Expander Graphs Courses Algorithm Analysis Courses Theoretical Computer Science Courses Derandomization Courses

Course Description

Overview

Explore the application of expander graphs in derandomization through this lecture from Carnegie Mellon University's graduate course "CS Theory Toolkit". Delve into how fully-explicit expander graphs can be utilized to decrease the error of randomized algorithms without significantly increasing the number of random bits used. Examine concepts such as error reduction, strongly explicit graphs, and algorithm analysis. Learn about random strings, set theory, and the magic trick of linear and exponential error decay in large expander graphs. Gain insights from resources like "Expander graphs and their applications" by Hoory, Linial, and Wigderson. Taught by Professor Ryan O'Donnell, this 23-minute lecture offers a comprehensive look at advanced topics in theoretical computer science.

Syllabus

Introduction
Error Reduction
Fully Explicit
Strongly Explicit
Algorithm A
Algorithm Analysis
Random Strings
Set B
Set L
Set S
Conclusion
Conclusions
Comparison
Magic trick
Linear error decay
Exponential error decay
Large Expander Graph


Taught by

Ryan O'Donnell

Related Courses

Randomized Methods in Complexity
Indian Institute of Technology Kanpur via Swayam
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Institute for Advanced Study via YouTube
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube
High-Precision Estimation of Random Walks in Small Space
IEEE via YouTube
Nearly Optimal Pseudorandomness From Hardness
IEEE via YouTube