BloomTech’s Downfall: A Long Time Coming

Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

High-Precision Estimation of Random Walks in Small Space

IEEE via YouTube

Start learning Write review

Overview

Limited-Time Offer: Up to 75% Off Coursera Plus!
7000+ certificate courses from Google, Microsoft, IBM, and many more.
India: 75% Off World: 40% Off
This course aims to teach learners how to achieve high-precision estimation of random walks in small space. The course covers topics such as comparing IntroRL vs. L via Pseudorandom Generators, Directed Graphs, Directed Laplacians, solving Laplacian systems, and derandomization via Laplacian solvers. The teaching method involves lectures and theoretical explanations. This course is intended for individuals interested in algorithms, graph theory, and random walks in computer science.

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

Reviews

Start your review of High-Precision Estimation of Random Walks in Small Space

Start learning

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.