### 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 language | English (US) |
---|---|

Title of host publication | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |

Publisher | IEEE Computer Society |

Pages | 81-89 |

Number of pages | 9 |

ISBN (Electronic) | 9781479965175 |

DOIs | |

State | Published - Dec 7 2014 |

Event | 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States Duration: Oct 18 2014 → Oct 21 2014 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

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

Country | United States |

City | Philadelphia |

Period | 10/18/14 → 10/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

*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