Computer Science/Discrete Mathematics Seminar I

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even \(n\), there exists an explicit bijection \(f\) from the \(n\)-dimensional Boolean cube to the Hamming ball of equal volume embedded in \((n+1)\)-dimensional Boolean cube, such that for all \(x\) and \(y\) it holds that \(\mathrm{distance}(x,y) / 5 \leq \mathrm{distance}(f(x),f(y)) \leq 4\, \mathrm{distance}(x,y)\) where \(\mathrm{distance}(\cdot,\cdot)\) denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive. This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. No prior knowledge is assumed. Joint work with Itai Benjamini and Igor Shinkar.