抽出器（数学）

この左側の頂点のサブセット（オレンジ色で強調表示）では、各頂点に接続された1本の辺がランダムに選択されます（赤色で強調表示）。これらの辺はそれぞれ右側の頂点に対応します。これは、1つのサブセットに対する1回のランダム選択に過ぎません。特定のサブセットの辺選択の実際のランダム性（均一分布への近さ）は、このプロセスを何度も実行することで近似できます。そして、すべての可能なサブセットの中で、右側の頂点の選択が最もランダムでない（均一分布から最も遠い）サブセットは、均一分布に近いです${\displaystyle \epsilon}$

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

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

抽出器を二変数関数として見ることも同等の方法です

${\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}$

抽出関数はもともと、弱い乱数源から乱数を抽出する 方法として研究されました。乱数抽出関数を参照してください。

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

参考文献

• ロネン・シャルティエル著「抽出装置の最近の進歩 - 概観」