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.
About this result
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

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading