抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
限られたメモリを有するアルゴリズムによってサンプリングされる弱いソースからランダムビットを抽出する問題を研究した。小型宇宙源のこのモデルを,Kamp,Rao,VadhanおよびZuckerman(STOC’06)によって紹介して,計算有界アルゴリズムによってサンプリングされる弱いソースからランダム性を抽出することに関して,TrevisanおよびVadhan(FOCS’00)によって開始する研究のラインに落下した。主な結果は次のものである。1)多項式誤差領域における小空間源に対する近最適抽出器を得た。nビット上の宇宙源のために,著者らの抽出器は,ちょうどk≧s.polylog(n)エントロピーを必要とする。これは,エントロピーk≧s1,1.2{log{0.51}n}(ChatopadhyayとLi,STOC’16)を必要とする以前の最良の結果の指数的改善である。2)無視できる誤差領域における小空間源のための改良抽出器を得た。nビット上の空間s源に対して,著者らの抽出器はエントロピーk>n1/2+δ.s1/2-δを必要とし,一方,以前の最良の結果はk>n2/3+δs1/3-δ(Chatopadhyay,Goodman,GoyalおよびLi,STOC’20)を必要とした。著者らの最初の結果を得るために,鍵成分は,小さな空間源からアフィン源への新しい低減であり,良好なアフィン抽出器を単純に適用することを可能にする。著者らの2番目の結果を得るために,著者らは,低エントロピーのために働く低誤差アフィン抽出器を持たないので,いくつかの新しい機械を開発する必要がある。著者らの主なツールは,ある種類の漏れ-回復抽出器(シリンダ交差抽出器として知られる)の新しい使用を,一般的タイプの極値設計と組み合わせることにより,単純なフレームワークによって構築される,敵対的ソースのための著しく改善された抽出器である。著者らの重要な成分は,これらの設計の最初の脱ランダム化であり,著者らは,符号化理論と付加的結合体に新しい接続を用いて得る。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
