检索结果-内蒙古大学图书馆

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第4期2卷 1078-1092页

作者： Mukherjee, Manuj Gelles, Ran Bar Ilan Univ Alexander Kofkin Fac Engn IL-5290002 Ramat Gan Israel

We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design interactive coding schemes that successfully perform any computation over these noisy networks and strive to reduce their communication overhead with respect to the original (noiseless) computation. A simple variant of a coding scheme by Rajagopalan and Schulman (STOC 1994) shows that any (noiseless) protocol of R rounds can be reliably simulated in O(Rlog n) rounds over a network with n = n(1)n(2) + 1 parties in which a single party is connected to n(2) noisy broadcast channels, each of which connects n(1) distinct parties. We design new coding schemes with improved overheads. Our approach divides the network into four regimes according to the relationship between n(1) and n(2). We employ a two-layer coding where the inner code protects each broadcast channel and is tailored to the specific conditions of the regime in consideration. The outer layer protects the computation in the network and is generally based on the scheme of Rajagopalan and Schulman, adapted to the case of broadcast channels. The overhead we obtain ranges from O(log log n(2)) to O(log n(2) log log n(1)/log n(1)) and beats the trivial O(log n) overhead in all four regimes.

关键词： Distributed communication multiparty interactive communication interactive coding

来源：评论

学校读者我要写书评

暂无评论

Deterministic and Efficient interactive coding from Hard-to-Decode Tree Codes 61

Deterministic and Efficient Interactive Coding from Hard-to-...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Brakerski, Zvika Kalai, Yael Tauman Saxena, Raghuvansh R. Weizmann Inst Sci Rehovot Israel Microsoft Boston MA USA MIT Boston MA USA Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781728196213

The field of interactive coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors (with constant information and error rates), remains an elusive open problem. An appealing approach towards resolving this problem is to construct an efficiently encodable and decodable combinatorial object called a tree code (Schulman, STOC 93). After a lot of effort in this direction, the current state of the art has deterministic constructions of tree codes that are efficiently encodable but require an alphabet of size logarithmic (instead of constant) in the depth of the tree code (Cohen, Haeupler, and Schulman, STOC 18). We emphasize that we still lack (even heuristic) candidate constructions that are efficiently decodable. In this work, we show that tree codes that are efficiently encodable, but not efficiently decodable, also imply deterministic and efficient interactive coding schemes that are resilient to adversarial errors. Our result immediately implies a deterministic and efficient interactive coding scheme with a logarithmic alphabet (i.e., 1/log log rate). We show this result using a novel implementation of hashing through deterministic tree codes that is powerful enough to yield interactive coding schemes.

关键词： interactive coding Tree Codes Communication Complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal interactive coding for Insertions, Deletions, and Substitutions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第10期65卷 5971-6000页

作者： Sherstov, Alexander A. Wu, Pei Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman et al. proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. For any epsilon > 0, they showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18 - epsilon, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 - epsilon, while keeping the alphabet to a constant size and the communication overhead to a constant factor. This resolves a question due to Gelles (2015). Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC '11).

关键词： interactive coding insertions and deletions edit distance tree codes communication complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient Multiparty interactive coding for Insertions, Deletions, and Substitutions [Extended Abstract] 19

Efficient Multiparty Interactive Coding for Insertions, Dele...

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Gelles, Ran Kalai, Yael Tauman Ramnarayan, Govind Bar Ilan Univ Ramat Gan Israel Microsoft Res Redmond WA USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450362177

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most epsilon/m fraction of the total communication, where m is the number of links in the network and epsilon is a small constant. This scheme assumes an oblivious adversary which is independent of the parties' inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to epsilon/m log m errors. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.

关键词： interactive coding distributed algorithms error correcting codes

来源：评论

学校读者我要写书评

暂无评论

interactive coding over the Noisy Broadcast Channel 2018

Interactive Coding over the Noisy Broadcast Channel

引用

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

作者： Efremenko, Klim Kol, Gillat Saxena, Raghuvansh Ben Gurion Univ Negev Beer Sheva Israel Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781450355599

A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only O(n log logn) rounds. The problem got resolved in 2005 by a seminal paper of Goyal, Kindler, and Saks, proving that Gallager's protocol is essentially optimal. We revisit the above noisy broadcast problem and showthat O(n) rounds suffice. This is possible due to a relaxation of the model assumed by the previous works. We no longer demand that exactly one player broadcasts in every round, but rather allow any number of players to broadcast. However, if it is not the case that exactly one player chooses to broadcast, each of the other players gets an adversely chosen bit. We generalized the above result and initiate the study of interactive coding over the noisy broadcast channel. We show that any interactive protocol that works over the noiseless broadcast channel can be simulated over our restrictive noisy broadcast model with constant blowup of the communication.

关键词： interactive coding Communication complexity Wireless broadcast

来源：评论

学校读者我要写书评

暂无评论

Optimal interactive coding for Insertions, Deletions, and Substitutions 58

Optimal Interactive Coding for Insertions, Deletions, and Su...

引用

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Sherstov, Alexander A. Wu, Pei Univ Calif Los Angeles Comp Sci Dept Los Angeles CA 90095 USA

ISBN: (纸本)9781538634646

interactive coding, pioneered by Schulman (FOCS '92, STOC '93), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky (2015) proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. They showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18, using a constant-size alphabet and a constant-factor overhead in communication. We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to 1/4 while keeping the alphabet to a constant size and the communication overhead to a constant factor. Our corruption tolerance matches an impossibility result for corruption rate 1/4 which holds even for substitutions alone (Braverman and Rao, STOC '11).

关键词： interactive coding communication complexity tree codes edit distance insertions and deletions

来源：评论

学校读者我要写书评

暂无评论

interactive coding for Multiparty Protocols 15

Interactive Coding for Multiparty Protocols

引用

6th Conference on Innovations in Theoretical Computer Science (ITCS)

作者： Jain, Abhishek Kalai, Yael Tauman Lewko, Allison Bishop Boston Univ Boston MA 02215 USA MIT Boston MA 02215 USA Microsoft Res Cambridge MA USA Columbia Univ New York NY USA

ISBN: (纸本)9781450333337

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOGS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of adversarial error, while blowing up the communication by only a constant factor. In this work we extend the work of Schulman to the multiparty setting. We show how to convert any (non-adaptive) n-party protocol into one that is resilient to Theta(1/n)-fraction of adversarial error, while blowing up the communication by only a constant factor. One might hope to get resilience to constant-fraction of errors, by restricting the adversary's error distribution, and allowing him to make at most a constant-fraction of errors per party. We present a black-box lower bound, showing that we cannot be resilient to such adversarial errors, even if we increase the communication by an arbitrary polynomial factor, assuming the error-resilient protocol has a fixed (non-adaptive) speaking order.

关键词： multiparty computation interactive coding

来源：评论

学校读者我要写书评

暂无评论

Fast interactive coding against Adversarial Noise

引用

JOURNAL OF THE ACM 2014年第6期61卷 35-35页

作者： Brakerski, Zvika Kalai, Yael Tauman Naor, Moni Stanford Univ Stanford CA 94305 USA Microsoft Res Philadelphia PA USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

Consider two parties who wish to communicate in order to execute some interactive protocol pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of (which was designed for an error-free channel). If pi only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol pi, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of pi (which we denote by N). In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(N), has failure probability roughly 2(-N), and is resilient to 1/32-fraction of adversarial error. The second runs in time 0(N log N), has failure probability roughly 2-N, and is resilient to some constant fraction of adversarial error. The third runs in time 0(N), has failure probability 1/poly(N), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made deterministic if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance). Categories and Subject Descriptors: E.4 [

关键词： Design Algorithms Theory interactive coding

来源：评论

学校读者我要写书评

暂无评论

The Rate of interactive Codes Is Bounded Away from 1 2023

The Rate of Interactive Codes Is Bounded Away from 1

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Efremenko, Klim Kol, Gillat Paramonov, Dmitry Saxena, Raghuvansh R. Ben Gurion Univ Negev Beer Sheva Israel Princeton Univ Princeton NJ USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450399135

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability epsilon > 0 independently, with only a 1 + O(root H(epsilon)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as epsilon goes to 0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as epsilon goes to 0, but retaining the assumption that the noiseless protocol is alternating. In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking. In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than 1. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors epsilon > 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS 2014].

关键词： interactive coding Communication Complexity Error Correcting Codes

来源：评论

学校读者我要写书评

暂无评论

Distributed CONGEST Algorithms against Mobile Adversaries 23

Distributed CONGEST Algorithms against Mobile Adversaries

引用

42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Fischer, Orr Parter, Merav Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9798400701214

In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network, analogous to a spread of a virus. Over the years, this setting has been studied mostly under the assumption that the communication graph is fully-connected. Resilient CONGEST algorithms for general graphs, on the other hand, are currently known only for the classical static setting, i.e., where the set of corrupted edges (or nodes) is fixed throughout the entire computation. We fill this missing gap by providing round-efficient simulations that translate given CONGEST algorithms into equivalent algorithms that are resilient against f-mobile edge adversaries, i.e., where the adversary controls a (possibly distinct) subset of f edges F-i in each round i. Our main results are: center dot Perfect-Security with Mobile Eavesdroppers. A translation of any r-round f-static-secure algorithm into an equivalent Theta(f)-mobile-secure algorithm with Theta(y) rounds. We also show that the f-static-secure algorithms of [Hitron, Parter and Yogev, DISC 2022 & ITCS 2023] can be modified into f-mobile-secure algorithms with the same number of rounds. center dot Resilience with Mobile Byzantine Adversaries. An f-mobile-byzantine simulation which is based on a decomposition of the graph into low-diameter edge-disjoint spanning trees. This provides us with near-optimal CONGEST compilers for expander graphs. It also leads to near-optimal compilers in the congested-clique model against Theta(n)-mobile adversaries. For general (2f + 1) edge-connected graphs with f-mobile adversary, we almost match the bounds known for the f-static setting, when provided a trusted pre-processing phase. Our results are based on a collection of tools borrowed from the area of interactive coding [Gelles, Found. Trends Theor. Comput. Sci. 2017], linear sketches and low-congestion graph decomposition. The introduced toolkit

关键词： CONGEST Fault Tolerance interactive coding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：