YoVDO

High-Precision Estimation of Random Walks in Small Space

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Graph Theory Courses Algorithms Courses Random Walks Courses Derandomization Courses

Course Description

Overview

Explore high-precision estimation techniques for random walks in constrained memory environments through this 25-minute IEEE conference talk. Delve into the comparison of RL and L using pseudorandom generators and graph algorithms, with a focus on directed graphs and Laplacians. Learn about solving Laplacian systems and their application in deterministic algorithms for ERWP. Examine the Eulerian case of ERWP via Laplacians and understand the algorithm outline. Investigate unit circle approximation and its definition for Laplacian matrices. Discover derandomization methods using Laplacian solvers and consider open problems and future research directions in this field.

Syllabus

Intro
RL vs. L via Pseudorandom Generators
RL vs. L via Graph Algorithms
Directed Graphs
Directed Laplacians Def: The Laplacian of G is L=1-W.
Solving Laplacian systems Lx = b
Application: Deterministic Algorithms for ERWP
ERWP via Laplacians: the Eulerian case
ERWP Algorithm Outline
Unit Circle Approximation Definition of Approximation for Laplacian Matrices
Derandomization via Laplacian solvers
Open problems and future directions


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

Graph Partitioning and Expanders
Stanford University via NovoEd
Tutorials for Complex Systems
Santa Fe Institute via Complexity Explorer
Algorithms for Big Data
Indian Institute of Technology Madras via Swayam
Random Walks
Santa Fe Institute via Complexity Explorer
Thermodynamics: Classical To Statistical
Indian Institute of Technology Guwahati via Swayam