TY - JOUR

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

AU - Benjamini, Itai

AU - Cohen, Gil

AU - Shinkar, Igor

N1 - Publisher Copyright:
© 2016, Hebrew University of Jerusalem.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - 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 ∈ N there exists an explicit bijection ψ: {0, 1}n → {x ∈ {0, 1}n+1 : |x| > n/2} such that for every x ≠ y ∈ {0, 1}n, (Formula presented.), 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 (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 (1997). We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. 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.

AB - 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 ∈ N there exists an explicit bijection ψ: {0, 1}n → {x ∈ {0, 1}n+1 : |x| > n/2} such that for every x ≠ y ∈ {0, 1}n, (Formula presented.), 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 (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 (1997). We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. 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.

UR - http://www.scopus.com/inward/record.url?scp=84971326427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84971326427&partnerID=8YFLogxK

U2 - 10.1007/s11856-016-1302-0

DO - 10.1007/s11856-016-1302-0

M3 - Article

AN - SCOPUS:84971326427

VL - 212

SP - 677

EP - 703

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 2

ER -