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.
High-Precision Estimation of Random Walks in Small Space
Overview
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
