Concept

# Disperser

Summary
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.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications

Related people

Related units