2 papers
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…
cs.CC2023
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…