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…
Refuting approaches to the log-rank conjecture for XOR functions
Hamed Hatami, Kaave Hosseini, Shachar Lovett +1
The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on poten…