Lesson plan
Extractor (mathematics)
) of a given subset's edge selections can be approximated by running the process many times, and the subset among all possible subsets that yields the least random (furthest from uniform distribution) selection of right vertices is \epsilon -close to uniform distribution. An (N,M,D,K,\epsilon) -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 that for 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 : [N] \times [D] \rightarrow [M] 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(X,U_D) is \epsilon -close to U_M , where U_T denotes the uniform distribution on [T] . 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.…
Article summary
) of a given subset's edge selections can be approximated by running the process many times, and the subset among all possible subsets that yields the least random (furthest from uniform distribution) selection of right vertices is \epsilon -close to uniform distribution. An (N,M,D,K,\epsilon) -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 that for 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 : [N] \times [D] \rightarrow [M] 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(X,U_D) is \epsilon -close to U_M , where U_T denotes the uniform distribution on [T] . 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.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.