6 papers · 1 filter
On the Advantage of Adaptivity for Sampling with Cell Probes
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We construct an explicit distribution over that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distr…
Hard-to-Sample Distributions from Robust Extractors
Farzan Byramji, Daniel M. Kane, Jackson Morris +1
We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notio…
Symmetric Distributions from Shallow Circuits
Daniel M. Kane, Anthony Ostuni, Kewen Wu
We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let be a Boolean fu…
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
Daniel Grier, Daniel M. Kane, Jackson Morris +2
We construct a family of distributions with over and a family of depth- quantum circuits such that …
Locally Sampleable Uniform Symmetric Distributions
Daniel M. Kane, Anthony Ostuni, Kewen Wu
We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let be a Boolean function where each outp…
Locality Bounds for Sampling Hamming Slices
Daniel M. Kane, Anthony Ostuni, Kewen Wu
Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distr…