Extractor (mathematics)

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