Extractor (mathematics)
id:
extractor-mathematics-191-7339364
title:
Extractor (mathematics)
text:
An -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, 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 ϵ -close to the uniform distribution in terms of total variation distance. A disperser is a related graph. An equivalent way to
brand slug:
wiki
category slug:
encyclopedia
description:
Bipartite graph with nodes
original url:
https://en.wikipedia.org/wiki/Extractor_(mathematics)
date created:
date modified:
2022-02-05T12:09:41Z
main entity:
{"identifier":"Q5422192","url":"https://www.wikidata.org/entity/Q5422192"}
image:
fields total:
13
integrity:
14