Locality Bounds for Sampling Hamming Slices
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914692838981632 |
|---|---|
| author | Kane, Daniel M. Ostuni, Anthony Wu, Kewen |
| author_facet | Kane, Daniel M. Ostuni, Anthony Wu, Kewen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14278 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Locality Bounds for Sampling Hamming Slices Kane, Daniel M. Ostuni, Anthony Wu, Kewen Computational Complexity Data Structures and Algorithms Quantum Physics 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. |
| title | Locality Bounds for Sampling Hamming Slices |
| topic | Computational Complexity Data Structures and Algorithms Quantum Physics |
| url | https://arxiv.org/abs/2402.14278 |