TY - GEN

T1 - Bi-lipschitz bijection between the boolean cube and the hamming ball

AU - Benjamini, Itai

AU - Cohen, Gil

AU - Shinkar, Igor

N1 - Publisher Copyright:
© 2014 IEEE.

PY - 2014/12/7

Y1 - 2014/12/7

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 such that for every x ≠ y {0,1}n it holds that 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 ofsampling distributions requires ideas beyond thesensitivity-based structural results of Boppana [IPL 97]. 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 such that for every x ≠ y {0,1}n it holds that 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 ofsampling distributions requires ideas beyond thesensitivity-based structural results of Boppana [IPL 97]. 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=84920051729&partnerID=8YFLogxK

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

U2 - 10.1109/FOCS.2014.17

DO - 10.1109/FOCS.2014.17

M3 - Conference contribution

AN - SCOPUS:84920051729

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 81

EP - 89

BT - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

PB - IEEE Computer Society

T2 - 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014

Y2 - 18 October 2014 through 21 October 2014

ER -