Daniel M. Kane

collaborators

5 papers

cs.CC2026

On the Advantage of Adaptivity for Sampling with Cell Probes

Farzan Byramji, Daniel M. Kane, Jackson Morris +1

We construct an explicit distribution $D$ over ${0, 1}^{N}$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distr…

cs.CC2026

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…

cs.CC2025

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 $f : {0, 1}^{m} \to {0, 1}^{n}$ be a Boolean fu…

cs.CC2025

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Daniel Grier, Daniel M. Kane, Jackson Morris +2

We construct a family of distributions ${D_{n}}_{n}$ with $D_{n}$ over ${0, 1}^{n}$ and a family of depth- $7$ quantum circuits ${C_{n}}_{n}$ such that $D_{n}$ …

cs.CC2025

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 $f : {0, 1}^{m} \to {0, 1}^{n}$ be a Boolean function where each outp…