抽出器（数学）

-抽出器は、左側にノード、右側にノードを持つ二部グラフで、左側の各ノードには (右側に) 隣接ノードがあり、サイズが少なくとも の左側の頂点の任意のサブセットに対して、 内のランダムなノードを選択し、ランダムなエッジをたどって右側のノード x を取得することによって得られる右側の頂点上の分布は、総変動距離に関して一様分布に - 近いという追加のプロパティがあります。 ${\displaystyle (N,M,D,K,\epsilon )}$${\displaystyle N}$${\displaystyle M}$${\displaystyle D}$${\displaystyle A}$${\displaystyle K}$${\displaystyle A}$${\displaystyle \epsilon}$

分散器は関連グラフです。

抽出器を2変量関数として見るのと同等の方法は、

${\displaystyle E:[N]\times [D]\rightarrow [M]}$

自然な方法で。この見方では、抽出子の特性は次と同等であることがわかります。最小エントロピーのビットを生成する任意の乱数ソースに対して、分布はに -近く、は上の一様分布を表します。 ${\displaystyle X}$${\displaystyle n}$ ${\displaystyle \log K}$${\displaystyle E(X,U_{D})}$${\displaystyle \epsilon}$${\displaystyle U_{M}}$${\displaystyle U_{T}}$${\displaystyle [T]}$

抽出器は、 に対する相対値が小さく、 が(入力ソース内の全体のランダム性) に可能な限り近い状態で構築できる場合に興味深いものになります。${\displaystyle K,D,\epsilon }$${\displaystyle N}$${\displaystyle M}$${\displaystyle KD}$

抽出関数はもともと、弱いランダム ソースからランダム性を抽出する 方法として研究されました。ランダム性抽出関数を参照してください。

確率的方法を使用すると、非常に優れたパラメータを持つ抽出グラフが存在することは簡単に示せます。課題は、優れたパラメータを持つそのようなグラフの明示的または多項式時間で計算可能な例を見つけることです。抽出グラフ (および分散グラフ) を計算するアルゴリズムは、コンピューター サイエンスで多くの用途が見出されています。

• ロネン・シャルティエル、抽出機の最近の開発 - 調査