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.

Official source

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

Related publications

Related units

No results

No results

Related people

Related courses

Related concepts

Related lectures

No results

No results

No results

No results