2 citations · 3 across the 7 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.CC2024
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…
cs.CC2024
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant such tha…
cs.CC2024
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…