Paper Info
Title
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
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 E N there exists an explicit bijection ψ: {0, 1}n → {x E {0, 1}n+1 : |x| > n/2} such that for every x ≠ y E {0, 1}n+1 it holds that 1/5 ≤ dist(ψ(x), ψ(y)) ≤ 4 5 - dist(x, y) where dist(·, ·) 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]. We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC°, but not in AC°. Moreover, we prove that ψ is “approximately local” in the sense that all but the last output bit of ψ are essentially determined by a single input bit.
Year
DOI
Venue
2014
10.1109/FOCS.2014.17
Foundations of Computer Science
Keywords
Field
DocType
Boolean functions,computational complexity,sampling methods,statistical distributions,Boolean cube,DLOGTIME-uniform TC°,Hamming distance,approximately local ψ,biLipschitz bijection,biLipschitz transitive Hamming ball,explicit bijection,input bit,low-level complexity classes,lower bounds,sampling distributions,sensitivity-based structural analysis
Boolean function,Discrete mathematics,Hamming code,Combinatorics,Bijection,Hamming(7,4),Hamming distance,Hamming bound,Hamming weight,Hamming graph,Mathematics
Conference
Volume
Issue
ISSN
212
2
0272-5428
Citations 
PageRank 
References 
0
0.34
8
Authors
3
Name
Order
Citations
PageRank
Itai Benjamini18114.91
Gil Cohen211916.43
Igor Shinkar3248.97