2 citations · 2 across the 8 of their papers we have counts for
11 papers
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 …
Quasipolynomial bounds for the corners theorem
Michael Jaber, Yang P. Liu, Shachar Lovett +2
Let be a finite abelian group and be a subset of which is corner--free, meaning that there are no and 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…
Corners in Quasirandom Groups via Sparse Mixing
Michael Jaber, Shachar Lovett, Anthony Ostuni
We improve the best known upper bounds on the density of corner-free sets over quasirandom groups from inverse poly-logarithmic to quasi-polynomial. We make similarly substantial i…
Strong Bounds for Skew-Corner-Free Sets
Michael Jaber, Shachar Lovett, Anthony Ostuni
Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of could be without containing a skew-corner: three points…
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…
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…
A tight lower bound on non-adaptive group testing estimation
Nader H. Bshouty, Tsun-Ming Cheung, Gergely Harcos +2
Efficiently counting or detecting defective items is a crucial task in various fields ranging from biological testing to quality control to streaming algorithms. The \emph{group te…