title: Disperser
text: # Disperser
  
  A disperser is a one-sided extractor. Where an extractor requires that every event gets the same probability under the uniform distribution and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event $A\subseteq \{0,1\}^{m}$ we have: $Pr_{U_{m}}[A]>1-\epsilon$
  
  Definition (Disperser): A $(k,\epsilon )$-disperser is a function
  
  $Dis:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}$
  
  such that for every distribution $X$ on $\{0,1\}^{n}$ with $H_{\infty }(X)\geq k$ the support of the distribution $Dis(X,U_{d})$ is of size at least $(1-\epsilon )2^{m}$.
  
  ## Graph theory
  
  An (N, M, D, K, e)-disperser is a bipartite graph with N vertices on the left side, each with degree D, and M vertices on the right side, such that every subset of K vertices on the left side is connected to more than (1 − e)M vertices on the right.
  
  An extractor is a related type of graph that guarantees an even stronger property; every (N, M, D, K, e)-extractor is also an (N, M, D, K, e)-disperser.
  
  ## Other meanings
  
  A disperser is a high-speed mixing device used to disperse or dissolve pigments and other solids into a liquid.
  
  