Computational Concentration of Measure: Optimal Bounds, Reductions, and More

Omid Etesami, Saeed Mahloujifar, Mohammad Mahmoody

Product measures of dimension $n$ are known to be concentrated in Hamming distance: for any set $S$ in the product space of probability $\epsilon$, a random point in the space, with proba…