CS Events
Computer Science Department ColloquiumTowards Optimal Sampling Algorithms |
|
||
Tuesday, March 19, 2024, 10:30am - 12:00pm |
|||
Speaker: Thuy-Duong “June” Vuong
Bio
Thuy-Duong “June” Vuong is a 5th year PhD student at Stanford. Her research is in designing and analyzing algorithms for sampling from complex high-dimensional distributions, with a focus on Markov chains analysis. Her work gives the optimal bounds on the runtime of Markov chains using entropy analysis and the theory of high-dimensional expanders. She received Bachelor of Science degrees in Mathematics and Computer Science at the Massachusetts Institute of Technology. Her research is supported by a Microsoft Research PhD fellowship.
Location : CoRE 301
:
Event Type: Computer Science Department Colloquium
Abstract: Sampling is a fundamental task with applications in various areas including physics, statistics, and combinatorics. Many applications involve the challenging task of sampling from complex high-dimensional distributions. Markov chains are a widely adopted approach for tackling these critical problems, but current runtime analyses are suboptimal.In this talk, I will introduce “entropic independence”, a novel and powerful framework for analyzing Markov chains, and use it to obtain the tightest possible runtime bounds. My work gives the first near-linear time sampling algorithms for classical statistical physics models in the tractable regime, resolving a 70-year-old research program. My research results in highly practical algorithms and settles several long-standing open problems in sampling and approximate computing.
:
Contact Assistant Professor Aaron Bernstein