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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

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

ISBN: (纸本)9781450380539

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still allows the parties to exchange their inputs? For the non-adaptive channel, where the parties must agree in advance on the order in which they communicate, the maximum error resilience was shown to be 1/4 (see Braverman and Rao, STOC 2011). The problem was also studied over the adaptive channel, where the order in which the parties communicate may not be predetermined (Ghaffari, Haeupler, and Sudan, STOC 2014;Efremenko, Kol, and Saxena, STOC 2020). These works show that the adaptive channel admits much richer set of protocols but leave open the question of finding its maximum error resilience. In this work, we show that the maximum error resilience of a protocol for message exchange over the adaptive channel is 5/16, thereby settling the above question. Our result requires improving both the known upper bounds and the known lower bounds for the problem.

关键词： Communication Complexity interactive coding Error Resilience

来源：评论

学校读者我要写书评

暂无评论

Optimal Short-Circuit Resilient Formulas

引用

JOURNAL OF THE ACM 2022年第4期69卷 26-26页

作者： Braverman, Mark Efremenko, Klim Gelles, Ran Yitayew, Michael Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Bar Ilan Univ Fac Engn Ramat Gan Israel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size thatworks correctly if less than 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction of 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present;these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists corruptions in up to a fraction of 1/5 of the transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes whose communication blowup is sub-exponential. Our coding scheme has taken a surprising inspiration from Blockchain technology.

关键词： Circuit complexity noise-resilient circuits interactive coding coding theory Karchmer-Wigderson games

来源：评论

学校读者我要写书评

暂无评论

Capacity Approaching coding for Low Noise interactive Quantum Communication 2018

Capacity Approaching Coding for Low Noise Interactive Quantu...

引用

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

作者： Leung, Debbie Nayak, Ashwin Shayeghi, Ala Touchette, Dave Yao, Penghui Yu, Nengkun Univ Waterloo C&O Waterloo ON Canada Univ Waterloo IQC Waterloo ON Canada Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Univ Technol Sydney FEIT CQSI Ultimo NSW Australia

ISBN: (纸本)9781450355599

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2(-Theta(n epsilon)) and uses a qudit channel n (1 + Theta(root epsilon)) times, of which an epsilon fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the root epsilon term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O(root epsilon log log 1/epsilon) in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS' 14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS' 14] for low..

关键词： Quantum Communication Complexity Quantum Information Theory coding Theory interactive coding Capacity

来源：评论

学校读者我要写书评

暂无评论

interactive Error Resilience beyond 2/7 2020

Interactive Error Resilience beyond 2/7

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

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

ISBN: (纸本)9781450369794

interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against? For the non-adaptive channel, where the parties must agree in advance on the order in which they communicate, Braverman and Rao prove that the maximum error resilience is 1/4 (STOC, 2011). Ghaffari, Haeupler, and Sudan (STOC, 2014) consider the adaptive channel, where the order in which the parties communicate may not be fixed, and give a clever protocol that is resilient to a 2/7 fraction of errors. This was believed to be optimal. We revisit this result, and show how to overcome the 2/7 barrier. Specifically, we show that, over the adaptive channel, every twoparty communication protocol can be converted to a protocol that is resilient to 7/24 > 2/7 fraction of errors with only a constant multiplicative overhead to the total communication. The protocol is obtained by a novel implementation of a feedback mechanism over the adaptive channel.

关键词： Communication Complexity interactive coding Error Resilience

来源：评论

学校读者我要写书评

暂无评论

Noisy Beeps 20

Noisy Beeps

引用

39th Symposium on Principles of Distributed Computing

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

ISBN: (纸本)9781450375825

We study the effect of noise on the n-party beeping model. In this model, in every round, each party may decide to either 'beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers a very simple abstraction of wireless networks and is very well suited for studying biological phenomena. Still, the noise resilience of the beeping model is yet to be understood. Our main result is a lower bound, showing that making protocols in the beeping model resilient to noise may have a large performance overhead. Specifically, we give a protocol that works over the (noiseless) beeping model, and prove that any scheme that simulates this protocol over the beeping model with correlated stochastic noise will blow up the number of rounds by an O(logn) multiplicative factor. We complement this result by a matching upper bound, constructing a noise-resilient simulation scheme with O(logn) overhead for any noiseless beeping protocol.

关键词： Communication Complexity Beeping Models Lower Bounds interactive coding Error-Correcting Codes Distributed Systems

来源：评论

学校读者我要写书评

暂无评论

The Infinite-Message Limit of Two-Terminal interactive Source coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第7期59卷 4071-4094页

作者： Ma, Nan Ishwar, Prakash Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94709 USA Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA

A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any finite number of messages, a single-letter characterization of the sum-rate-distortion function was established in previous works using standard information-theoretic techniques. This, however, does not provide a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic analysis in distributed block source coding involving potentially an infinite number of infinitesimal-rate messages. In this paper, the infinite-message sum-rate-distortion function, viewed as a functional of the joint source distribution and the distortion levels, is characterized as the least element of a partially ordered family of functionals having certain convex-geometric properties. The new characterization does not involve evaluating the infinite-message limit of a finite-message sum-rate-distortion expression. This characterization leads to a family of lower bounds for the infinite-message sum-rate-distortion expression and a simple criterion to test the optimality of any achievable infinite-message sum-rate-distortion expression. The new convex-geometric characterization is used to develop an iterative algorithm for evaluating any finite-message sum-rate-distortion function. It is also used to construct the first examples which demonstrate that for lossy source reproduction, two messages can strictly improve the one-message Wyner-Ziv rate-distortion function settling an unresolved question from a 1985 paper. It is shown that a single backward message of arbitrarily small rate can lead to an arbitrarily large gain in the sum-rate.

关键词： Alternating convexification Boolean AND communication complexity distributed source coding function computation interactive coding Wyner-Ziv coding

来源：评论

学校读者我要写书评

暂无评论

Reliable communication over highly connected noisy networks

引用

DISTRIBUTED COMPUTING 2019年第6期32卷 505-515页

作者： Alon, Noga Braverman, Mark Efremenko, Klim Gelles, Ran Haeupler, Bernhard Tel Aviv Univ Sackler Sch Math IL-69978 Tel Aviv Israel Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Bar Ilan Univ Fac Engn IL-52900 Ramat Gan Israel Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding scheme that takes R rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate, i.e., while keeping lim infn, R.8 R/ R positive. Rajagopalan and Schulman (STOC'94) were the first to consider this question, and provided a coding scheme with rate O(1/ log(d + 1)), where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is O(1/ log n), which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a (d-regular) network has mixing time m, then there exists an efficient coding scheme with rate O(1/ m3 logm). This implies a constant rate coding scheme for any n-party protocol over a d-regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees nO(1).

关键词： coding theory Random noise interactive coding Computation with noise

来源：评论

学校读者我要写书评

暂无评论

Making asynchronous distributed computations robust to noise

引用

DISTRIBUTED COMPUTING 2019年第5期32卷 405-421页

作者： Censor-Hillel, Keren Gelles, Ran Haeupler, Bernhard Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Bar Ilan Univ Fac Engn IL-52900 Ramat Gan Israel Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating an optimal corruption of a Theta(1/n) fraction of all messages and incurring a moderate blowup of O(nlog2n) in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.

关键词： interactive coding Computation with noise Adversarial noise

来源：评论

学校读者我要写书评

暂无评论

Radio Network coding Requires Logarithmic Overhead 60

Radio Network Coding Requires Logarithmic Overhead

引用

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

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

ISBN: (纸本)9781728149523

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, meaning that it was the only neighbor broadcasting. While the (noiseless) radio network model received a lot of attention over the last few decades, the effect of noise on radio networks is still not well understood. In this paper, we take a step forward and show that making radio network protocols resilient to noise may require a substantial performance overhead. Specifically, we construct a multi -hop network and a communication protocol over this network that works in T rounds when there is no noise. We prove that any scheme that simulates our protocol and is resilient to stochastic noise, requires at least cT log(n) rounds, for some constant c. This stands in contrast to our previous result (STOC, 2018), showing that protocols over the single -hop (clique) network can be made noise resilient with only a constant overhead. Our result also settles a recent conjecture by Censor-Hillel, Haeupler, Hershkowitz, Zuzic (2018). We complement the above result by giving a scheme to simulate any protocol with a fixed order of transmissions with only an O(log (n)) overhead.

关键词： interactive coding Wireless Broadcast Lower Bounds Communication Complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal Short-Circuit Resilient Formulas 34

Optimal Short-Circuit Resilient Formulas

引用

34th Computational Complexity Conference (CCC)

作者： Braverman, Mark Efremenko, Klim Gelles, Ran Yitayew, Michael A. Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Ben Gurion Univ Negev Comp Sci Dept Beer Sheva Israel Bar Ilan Univ Fac Engn Ramat Gan Israel

ISBN: (纸本)9783959771160

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present;these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.

关键词： Circuit Complexity Noise-Resilient Circuits interactive coding coding Theory Karchmer-Wigderson Games

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：