Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
复制标题
布尔立方体和汉明球之间的 Bi-Lipschitz 双射
DOI：
10.1007/s11856-016-1302-0
复制
发表时间：
2016
影响因子：
1
通讯作者：
Igor Shinkar
中科院分区：
文献类型：
--
作者：
I. Benjamini;Gil Cohen;Igor Shinkar
我们构造了一个从布尔立方体到等体积Hamming球的双Lipschitz双射。更确切地说，我们证明了对于所有的偶数n∈N，存在一个显式双射ψ：{0，1}n→{x∈{0，1}n+1：|x|>；N/2}使得对于每个x≠y∈{0，1}n，\DocumentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setLong{\oddsidemarin}{-69pt}\Begin{Document}$\FRAC{1}{5}\leqslant\FRAC{{dis\tan ce\Left(x\)，右(x\)\psi\Left(y\right)}\right)}{{dis\tan ce\Left({x，y}\right)}}\leqslant 4，$$\end{Document}其中距离(·，·)表示汉明距离。特别地，这意味着Hamming球是双Lipschitz传递的。这一结果有力地否定了Lovett和Viola(2012)的一个公开问题，他们在低水平复杂性类的抽样分布的背景下提出了这个问题。它的概念含义是，在抽样分布的背景下证明下限的问题需要超越Boppana(1997)基于敏感性的结构结果的想法。我们进一步研究了映射ψ，证明了它(及其逆)在DLOGTIME-一致TC0中是可计算的，但在AC0中是不可计算的。此外，我们还证明了ψ是“近似局部的”，即ψ的除最后一个输出位之外的所有位基本上都由一个输入位决定。
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, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{5} \leqslant \frac{{dis\tan ce\left( {\psi \left( x \right),\psi \left( y \right)} \right)}}{{dis\tan ce\left( {x,y} \right)}} \leqslant 4,$$\end{document} 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.