YoVDO

Faster Polytope Rounding, Sampling, and Volume Computation via a Sublinear Ball Walk

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithm Analysis Courses Markov Chains Courses Probability Theory Courses Computational Geometry Courses Optimization Algorithms Courses

Course Description

Overview

Explore advanced mathematical concepts in this 18-minute IEEE conference talk on accelerating polytope-related computations. Delve into the innovative "Ball Walk" algorithm, which offers sublinear implementation for faster polytope rounding, sampling, and volume computation. Learn about current bottlenecks in Markov chains, discover the key results, and understand why this approach works with high probability. Examine the faster implementation techniques, analyze running times and expected costs, and investigate the anti-concentration lemma. Conclude by exploring future directions in this cutting-edge area of computational geometry and probability theory.

Syllabus

Intro
Current bottleneck
Markov chains
Results
Algorithm overview
Sublinear implementation
Why does it work
High probability
Faster implementation
Running time
Expected cost
Bound expected waiting time
Anti concentration lemma
Future directions


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

Probability - The Science of Uncertainty and Data
Massachusetts Institute of Technology via edX Introduction to Probability, Statistics, and Random Processes
University of Massachusetts Amherst via Independent Bioinformatique : algorithmes et génomes
Inria (French Institute for Research in Computer Science and Automation) via France Université Numerique Algorithms for Big Data
Indian Institute of Technology Madras via Swayam Quantitative Model Checking
EIT Digital via Coursera