文献

J-GLOBAL ID：202202229330763262   整理番号：22A0917449

雑音のあるブロードキャストネットワークにおける一般計算のためのタイトな限界【JST・京大機械翻訳】

Tight Bounds for General Computation in Noisy Broadcast Networks

著者 (4件)： Efremenko Klim (Ben-Gurion University,Beer Sheva,Israel) ,  Kol Gillat (Princeton University,Princeton,USA) ,  Paramonov Dmitry (Princeton University,Princeton,USA) ,  Saxena Raghuvansh R. (Princeton University,Princeton,USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 634-645  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： IIは,各ラウンドにおいて,事前指定パーティがシンボルを他のすべての関係者に放送する,n-パーティブロードキャストチャネル上のプロトコルである。入力としてプロトコルIIを入力し,雑音耐性プロトコルIIを出力する方式を設計し,各受信シンボルを固定定数確率で独立にフリップした。何れかのそのようなシミュレーション方式によって発生するラウンドの数における最小オーバヘッドである。80年代からのGallgerによる古典的結果は,あらゆるラウンドで通信されたビットが通信履歴に無関係である,非対話型Tラウンドプロトコルが,ラウンドの数においてO(loglogT)乗法オーバヘッドだけを有するノイズ弾力性のものに変換することができることを示した。どのプロトコルでも同じように証明された。Orは,そのシミュレーションがΩ(logT)オーバヘッド(常にサフィス)を必要とするプロトコルである。負における上記の質問に答えた:著者らは,あらゆるプロトコルとチャネルアルファベットのためにO(√logT)オーバヘッドを有するシミュレーション方式を与えた。また,T=nと多項式アルファベットによるポインタチャッシングプロトコルをシミュレートするのに必要なオーバヘッドに対するΩ(√logT)の下限を整合することを証明した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *雑音 ,  シミュレーション ,  多項式 ,  *ネットワーク ,  弾性 ,  乗算 ,  雑音安定度 ,  チャネル ,  *ブロードキャスト
準シソーラス用語： オーバヘッド ,  通信履歴 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 雑音 ,  ブロードキャスト ,  計算 ,  限界