From the 2 of 9 linked papers with an AI index.
9 papers
Space-Entropy Lower Bounds for Random Sampling
Thomas L. Draper, Feras A. Saad
The paper establishes fundamental lower bounds on the memory required by exact random sampling algorithms that aim to use near-optimal amounts of random bits, showing that achievin…
Online Random Sampling with Real Probabilities
Thomas L. Draper, David G. Harris, Feras A. Saad
The paper presents an online algorithm that samples from a sequence of discrete distributions using only fair coin flips, achieving near‑optimal entropy usage while using only loga…
GradInf: Gradient Estimation as Probabilistic Inference
Gaurav Arya, Mathieu Huot, Moritz Schauer +2
Gradient estimation -- the task of computing the gradient of the expected value of a probabilistic program -- has diverse applications in scientific computing, but is notoriously d…
Efficient Online Random Sampling via Randomness Recycling
Thomas L. Draper, Feras A. Saad
This article studies the fundamental problem of using i.i.d. coin tosses from an entropy source to efficiently generate random variables , where $(P_1, P_…
Efficient Rejection Sampling in the Entropy-Optimal Range
Thomas L. Draper, Feras A. Saad
We study the problem of generating a random variate from a finite discrete probability distribution using an entropy source of independent fair coin flips. A classic result…
Analyzing Decoders for Quantum Error Correction
Abtin Molavi, Feras Saad, Aws Albarghouthi
Quantum error correction (QEC) enables reliable computation on noisy hardware by encoding logical information across many physical qubits and periodically measuring parities to det…