Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-031 | 27th February 2024 06:36

Locality Bounds for Sampling Hamming Slices

RSS-Feed




Revision #1
Authors: Daniel Kane, Anthony Ostuni, Kewen Wu
Accepted on: 27th February 2024 06:36
Downloads: 29
Keywords: 


Abstract:

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 distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed.



Changes to previous version:

Minor updates to better reflect past literature. No technical material has been changed.


Paper:

TR24-031 | 22nd February 2024 06:31

Locality Bounds for Sampling Hamming Slices





TR24-031
Authors: Daniel Kane, Anthony Ostuni, Kewen Wu
Publication: 22nd February 2024 16:44
Downloads: 149
Keywords: 


Abstract:

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 distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed.



ISSN 1433-8092 | Imprint