Sampling Tools and the Power of AC0Research Paper
A sampler is a device that turns uniform random bits into a sample of a target distribution. Asking which distributions a restricted class of devices can sample, exactly or approximately, is the sampling analogue of asking which functions it can compute. The two questions behave differently: some distributions that look hard can be sampled by very weak…