首页    期刊浏览 2024年12月13日 星期五
登录注册

文章基本信息

  • 标题:Interactive Coding with Constant Round and Communication Blowup
  • 本地全文:下载
  • 作者:Klim Efremenko ; Elad Haramaty ; Yael Kalai
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency. All these works assume that in each round each party sends a single bit, an assumption that may cause a substantial increase in the {\em round complexity}. Moreover, they assume that the communication complexity of the underlying protocol is {\em fixed} and a priori known.

    In this work, we show how to convert any protocol , with {\em no a priori} known {\em communication bound}, into an error-resilient protocol , with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the {\em round complexity} by at most a constant factor. We consider the model where in each round each party may send a message of {\em arbitrary length}, where the length of the messages and the length of the protocol may be {\em adaptive}, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where -fraction of the communication may be corrupted, where we allow each corruption to be an {\em insertion} or {\em deletion} (in addition to toggle).

    In addition, we try to minimize the blowup parameters: In particular, we construct such with (1 + O 1 4 ) blowup in communication and O (1) blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct where both the blowup in rounds and communication, approaches one (i.e., no blowup) as approaches zero. We give ``evidence" that our parameters are ``close to" optimal.

国家哲学社会科学文献中心版权所有