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

Itai Benjamini, Gil Cohen, Igor Shinkar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 ∈ 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.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Pages81-89
Number of pages9
ISBN (Electronic)9781479965175
DOIs
StatePublished - Dec 7 2014
Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
Duration: Oct 18 2014Oct 21 2014

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
CountryUnited States
CityPhiladelphia
Period10/18/1410/21/14

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Bi-lipschitz bijection between the boolean cube and the hamming ball'. Together they form a unique fingerprint.

  • Cite this

    Benjamini, I., Cohen, G., & Shinkar, I. (2014). Bi-lipschitz bijection between the boolean cube and the hamming ball. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 81-89). [6978992] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2014.17