2
[2402.14278] Locality Bounds for Sampling Hamming Slices
source link: https://arxiv.org/abs/2402.14278
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
[Submitted on 22 Feb 2024 (v1), last revised 27 Feb 2024 (this version, v2)]
Locality Bounds for Sampling Hamming Slices
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.
| Comments: | Minor updates to better reflect past literature. No technical material has been changed |
| Subjects: | Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Quantum Physics (quant-ph) |
| Cite as: | arXiv:2402.14278 [cs.CC] |
| (or arXiv:2402.14278v2 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2402.14278 |
Submission history
From: Anthony Ostuni [view email][v1] Thu, 22 Feb 2024 04:36:49 UTC (416 KB)
[v2] Tue, 27 Feb 2024 04:45:29 UTC (417 KB)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK