56 min
Seminar, Hosted by Simons Institute for the Theory of Computing
Sampling elements of a finite group: efficiency of the product replacement algorithm with accumulator
- Mathematics, Algebra and
Recording
Abstract
A refinement of the product replacement algorithm aims to draw nearly uniform elements from a finite group. This talk studies how many steps are needed for the output distribution to approach uniformity, using spectral-gap estimates and computer-assisted calculations in joint work with Michał Marcinkowski.
Topics
- product replacement algorithm, search World Wide
- nearly uniform elements, search World Wide
- finite group
- output distribution, search World Wide
- uniformity, search World Wide
- spectral-gap estimates, search World Wide
- computer-assisted calculations, search World Wide
- Michał Marcinkowski, search World Wide
- refinement, search World Wide