Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

DOI10.1007/S11856-016-1302-0zbMATH Open1341.05012OpenAlexW2406726738MaRDI QIDQ2630133FDOQ2630133

Authors Itai Benjamini, Gil Cohen, Igor Shinkar

Publication date 25 July 2016

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.2017

zbMATH Keywords

computational complexityBoolean circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial identities, bijective combinatorics (05A19)

Abstract: 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 distance(x,y) / 5 <= distance(f(x),f(y)) <= 4 distance(x,y) where distance(,) 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 will require some new ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. We study the mapping f further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. Moreover, we prove that f is "approximately local" in the sense that all but the last output bit of f are essentially determined by a single input bit.

Recommendations

• Lipschitz bijections between boolean functions
• On Lipschitz bijections between Boolean functions
• Bi-Lipschitz bijections of \(\mathbb Z\)
• Sampling lower bounds: Boolean average-case and permutations
• The metric geometry of the Hamming cube and applications

Cites work

• scientific article; zbMATH DE number 4066951 (Why is no real title available?)
• scientific article; zbMATH DE number 1789916 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• scientific article; zbMATH DE number 3065933 (Why is no real title available?)
• A course in combinatorics.
• A note on the edges of the n-cube
• A phase transition for the metric distortion of percolation on the hypercube
• Boolean functions with low average sensitivity depend on few coordinates
• Bounded-depth circuits cannot sample good codes
• Extractors for circuit sources
• Geometric properties of Poisson matchings
• Log Space Recognition and Translation of Parenthesis Languages
• On the implementation of huge random objects
• Optimal numberings and isoperimetric problems on graphs
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• The average sensitivity of bounded-depth circuits
• The complexity of distributions

Cited in

(7)

• On mappings on the hypercube with small average stretch
• On the failure of concentration for the \(\ell_\infty\)-ball
• Lipschitz bijections between boolean functions
• Approximate homomorphisms between the Boolean cube and groups of prime order
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Sampling lower bounds: Boolean average-case and permutations
• On Lipschitz bijections between Boolean functions

This page was built for publication: Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2630133)