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)

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.

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

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

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)

Cites Work

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

Cited In (7)

• On the failure of concentration for the \(\ell_\infty\)-ball
• On mappings on the hypercube with small average stretch
• Lipschitz bijections between boolean functions
• Sampling lower bounds: Boolean average-case and permutations
• Title not available (Why is that?)
• On Lipschitz bijections between Boolean functions
• Approximate homomorphisms between the Boolean cube and groups of prime order

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)