Extractor

An $\left(N,M,D,K,epsilon\right)$ -extractor is a bipartite graph with $N$ nodes on the left and $M$ nodes on the right such that each node on the left has $D$ neighbors (on the right), which has the added property thatfor any subset $A$ of the left vertices of size at least $K$, the distribution on right vertices obtained by choosing a random node in $A$ and then following a random edge to get a node x on the right side is $epsilon$-close to the uniform distribution in terms of total variation distance.

A disperser is a related graph.

An equivalent way to view an extractor is as a bivariate function

:$E : \left[N\right] imes \left[D\right] ightarrow \left[M\right]$

in the natural way. With this view it turns out that the extractor property is equivalent to: for any source of randomness $X$ that gives $n$ bits with min-entropy $log K$, the distribution $E\left(X,U_D\right)$ is $epsilon$-close to $U_M$, where $U_T$ denotes the uniform distribution on $\left[T\right]$.

Extractors are interesting when they can be constructed with small $K,D,epsilon$ relative to $N$ and $M$ is as close to $KD$ (the total randomness in the input sources) as possible.

Extractor functions were originally researched as a way to "extract" randomness from weakly random sources. "See" randomness extractor.

Using the probabilistic method it is easy to show that extractor graphs with really good parameters exist. The challenge is to find explicit or polynomial time computable examples of such graphs with good parameters. Algorithms that compute extractor (and disperser) graphs have found many applications in computer science.

References

* Ronen Shaltiel, [http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps Recent developments in extractors] - a survey

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• extractor — ex‧trac‧tor [ɪkˈstræktə ǁ ər] noun [countable] 1. a machine that removes dirt, dust etc from the air: • a steam extractor that fits neatly into the ceiling • By not having extractor fans we re breaking Health and Safety regulations. 2.… …   Financial and business terms

• Extractor — Saltar a navegación, búsqueda Extractor mecánico El extractor mecánico es una herramienta manual que se utiliza básicamente para extraer las poleas, engranajes o cojinetes de los ejes, cuando están muy apretados y no salen con la fuerza de las… …   Wikipedia Español

• extractor — EXTRACTÓR, OÁRE, extractori, oare, adj. s.n. I. adj. Care extrage sau ajută la extragerea anumitor substanţe sau corpuri. II. s.n. 1. Aparat cu ajutorul căruia se efectuează o extracţie (2). ♦ Aparat cu care se extrage mierea din faguri. 2.… …   Dicționar Român

• extractor — extractor, ra (De extracto). 1. m. y f. Persona que extrae. 2. m. Aparato o pieza de un mecanismo que sirve para extraer. 3. f. extractor (ǁ aparato que sirve para extraer). ☛ V. campana extractor …   Diccionario de la lengua española

• extractor — instrumento usado para resolver un cálculo o cuerpo extraño Diccionario ilustrado de Términos Médicos.. Alvaro Galiano. 2010. extractor Instrumento médico, como las pinzas, que se utiliza …   Diccionario médico

• extractor — extractor, ra adjetivo,sustantivo masculino 1. Que sirve para extraer: Ha comprado un extractor para la cocina. campana* extractora …   Diccionario Salamanca de la Lengua Española

• Extractor — Ex*tract or, n. 1. One who, or that which, extracts; as: (a) (Surg.) A forceps or instrument for extracting substances. (b) (Breech loading Firearms) A device for withdrawing a cartridge or spent cartridge shell from the chamber of the barrel.… …   The Collaborative International Dictionary of English

• Extractor — Extractor, so v.w. Ventilator …   Pierer's Universal-Lexikon

• extractor — |àtô| adj. 1. Que extrai; que extrata. • s. m. 2. Utensílio para extrair do cano da arma o cartucho queimado.   ♦ [Portugal] Grafia de extrator antes do Acordo Ortográfico de 1990.   ♦ Grafia no Brasil: extrator …   Dicionário da Língua Portuguesa

• extractor — ► NOUN 1) a machine or device used to extract something. 2) (before another noun ) denoting a fan or other device for extracting odours and stale air …   English terms dictionary

• extractor — [ek strak′tər, ikstrak′tər] n. a person or thing that extracts; specif., the part of a breech loading gun that withdraws the cartridge or shell case from the chamber …   English World dictionary