• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
【24h】

Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming

机译：信息复杂性与腐败的关系及其在正交性和空洞化中的应用

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these techniques involve properties of large sub-matrices (rectangles) of the truth-table matrix defining a communication problem. The only technique that does not quite fit is information complexity, which has been investigated over the last decade. Here, we connect information complexity to one of the most powerful "rectangular" techniques: the recently-introduced smooth corruption (or "smooth rectangle") bound. We show that the former subsumes the latter under rectangular input distributions. As an application, we obtain an optimal Ω (n) lower bound on the information complexity-under the uniform distribution-of the so-called orthogonality problem (ORT), which is in turn closely related to the much-studied Gap-Hamming-Distance problem (GHD). The proof of this bound is along the lines of recent communication lower bounds for GHD, but we encounter a surprising amount of additional technical detail.
机译：在通信复杂度方面的三十年研究导致发明了许多技术来降低随机通信的复杂度。这些技术中的大多数涉及定义通信问题的真值表矩阵的大子矩阵（矩形）的属性。唯一不太适合的技术是信息复杂性，最近十年对此进行了研究。在这里，我们将信息复杂性与最强大的“矩形”技术之一联系：最近引入的平滑破坏（或“平滑矩形”）边界。我们显示前者在矩形输入分布下包含了后者。作为应用，我们在均匀分布的情况下获得了所谓的正交性问题（ORT）的信息复杂度的最优Ω（n）下界，而该问题又与广为研究的Gap-Hamming-距离问题（GHD）。这个界限的证明遵循了GHD最近的通信下限，但是我们遇到了令人惊讶的其他技术细节。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号