• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
【24h】

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

机译：布尔多维数据集和汉明球之间的双Lipschitz双射

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：我们构造了一个从布尔立方体到相等体积的汉明球的bi-Lipschitz双射，更确切地说，我们证明了对于所有偶数n∈N都存在一个明确的双射，使得对于每个x≠y {0,1} n认为其中dist（。，。）表示汉明距离，特别是这意味着汉明球是bi-Lipschitz可传递的。这个结果对Lovett和Viola [CC 2012]的一个开放问题给出了强有力的否定答案，他们在低级复杂度类别的抽样分布的背景下提出了这个问题。抽样分布的背景需要超越Boppana基于灵敏度的结构结果的观点[IPL 97]。我们进一步研究了映射ψ，并证明它（及其逆矩阵）在DLOGTIME统一的TC0中是可计算的，但在AC0中不是可计算的。此外，从prove的最后一个输出位基本上由单个输入位确定的意义上说，我们证明了ψ是“近似局部的”。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号