分散機

分散器は片側抽出器です。^[1]抽出器では、すべてのイベントが均一分布と抽出された分布の下で同じ確率になることが要求されますが、分散器では後者のみが要求されます。したがって、分散器の場合、イベントは次のようになります。 ${\displaystyle A\subseteq \{0,1\}^{m}}$${\displaystyle Pr_{U_{m}}[A]>1-\epsilon }$

定義（分散器）：分散 器 は関数である${\displaystyle (k,\epsilon )}$

${\displaystyle Dis:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}}$

上の任意の分布に対して、分布のサポートのサイズが少なくとも となるような分布です。 ${\displaystyle X}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle H_{\infty }(X)\geq k}$ ${\displaystyle Dis(X,U_{d})}$ ${\displaystyle (1-\epsilon )2^{m}}$

( N , M , D , K , e )-分散グラフは、左側にそれぞれ次数Dの N頂点があり、右側にM頂点があり、左側のK頂点のすべてのサブセットが右側の (1 − e ) M を超える頂点に接続されている二部 グラフです。

抽出子は、さらに強力な特性を保証するグラフの関連タイプです。すべての( N、M、D、K、e )-抽出子は、 ( N、M、D、K、e )-分散子でもあります。

分散機は、顔料やその他の固体を液体に分散または溶解するために使用される高速混合装置です。

• エキスパンダーグラフ