首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:Certifying Equality With Limited Interaction
  • 本地全文:下载
  • 作者:Joshua Brody ; Amit Chakrabarti ; Ranganath Kondapally
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The \textsc{equality} problem is usually one's first encounter withcommunication complexity and is one of the most fundamental problems inthe field. Although its deterministic and randomized communicationcomplexity were settled decades ago, we find several new things to sayabout the problem by focusing on two subtle aspects. The first is toconsider the {\em expected} communication cost (at a worst-case input)for a protocol that uses limited interaction---i.e., a bounded number ofrounds of communication---and whose error probability is zero or closeto it. The second is to consider the {\em information cost} of suchprotocols. We obtain asymptotically optimal rounds-versus-cost tradeoffsfor \textsc{equality}: both expected communication cost and informationcost scale as (logloglogn), with r−1 logs, where ris the number of rounds. For the case of zero-error communication cost,we obtain essentially matching bounds, up to a tiny additive constant.

  • 关键词:Communication complexity; direct sum; disjointness; Equality; information complexity; information theory; lower bounds; rounds
国家哲学社会科学文献中心版权所有