文献

J-GLOBAL ID：202202210588429307   整理番号：22A0917487

コイン問題のタイトスペース複雑性【JST・京大機械翻訳】

Tight Space Complexity of the Coin Problem

著者 (3件)： Braverman Mark (Princeton University) ,  Garg Sumegha (Harvard University) ,  Zamir Or (Institute for Advanced Study)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 1068-1079  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： コイン問題において,確率1/2-βを持つヘッドである確率1/2+βのヘッドである,n.i.d.coins間の確率が少なくとも2/3であると識別するよう依頼した。コイン問題の空間複雑性に関心があり,その問題を解いた読取り分岐プログラムの幅に対応した。コイン問題はβが小さくなるにつれてより困難になる。統計的には,計数を用いてβ=Ω(n-1/2)がいつでも解くことができる。以前に,β=O(n-1/2)に対して,計数は本質的に最適(等価,幅ポリ(n)が[Braverman-Garg-Wooddruff FOCS’20])であることを示した。一方,コイン問題は,任意の一定のc>log_2(√5-1)≒0.306(AND-ORツリーの低幅シミュレーション)に対して,β>n-cのO(logn)幅のみを必要とする。本論文では,限界間のギャップを閉じて,O(logn)幅サフスのβ=n-c値と,c=1/3の遷移を伴うポリ(n)幅を必要とする領域の間の厳密な閾値を示した。これは,バイアスβのすべての値に対して,コイン問題を解くメモリ複雑性の完全なキャラクタリゼーション(一定因子まで)を与える。両方の限界に新しい技術を導入した。上界では,サイズlognビットのメモリスタックを必要としない再帰大多数に基づく構築を与えた。下界では,読出分岐プログラムにおける成功確率の進行を解析するための新しい組合せ技術を導入した。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件)： コイン ,  問題 ,  タイ ,  複雑性