Locality Bounds for Sampling Hamming Slices

The complexity of distributions (tag) has seen a lot of activity and exciting progress, including [Vio12b, LV12, Vio14, DW11, BIL12, BCS14, Vio12c,  Vio20, CGZ21, Vio23, YZ24, FLRS23, RS24, DMK24] and connections to extractors [CZ16, Li16, CS16, Coh16, BDT16], data structures, and quantum-classical separations [WP23]. One of the problems considered in [Vio12b] is that of sampling the uniform distribution over strings of weight with small locality or depth. Two bounds are proved […]