Экстрактор (математика)

Ан $(N,M,D,K,\epsilon )$ - экстрактор представляет собой двудольный граф с $N$ узлы слева и $M$ узлы справа так, что каждый узел слева имеет $D$ соседи (справа), у которого есть добавленное свойство, котороедля любого подмножества $A$ левых вершин размером не менее $K$, распределение по правым вершинам, полученное выбором случайного узла в $A$ а затем следовать по случайному ребру , чтобы получить узел x с правой стороны, это $\epsilon$-близкое к равномерному распределению по общему расстоянию вариации .

Дисперсия — это связанный граф.

Эквивалентный способ просмотра экстрактора — это двумерная функция.

$E:[N]\times [D]\rightarrow [M]$

естественным путем. С этой точки зрения оказывается, что свойство экстрактора эквивалентно: для любого источника случайности $X$ это дает $n$ биты с минимальной энтропией $\log K$, распределение $E(X,U_{D})$ является $\epsilon$-близко к $U_{M}$, где $U_{T}$ обозначает равномерное распределение на $[T]$.

Экстракторы интересны, когда их можно сконструировать с помощью небольших $K,D,\epsilon$ относительно $N$ и $M$ настолько близок к $KD$ (общая случайность во входных источниках), насколько это возможно.

Функции экстрактора изначально исследовались как способ извлечь случайность из слабослучайных источников. См. экстрактор случайности .

Используя вероятностный метод , легко показать, что графы-экстракторы с действительно хорошими параметрами существуют. Задача состоит в том, чтобы найти явные или полиномиально вычислимые примеры таких графов с хорошими параметрами. Алгоритмы, вычисляющие графы экстракторов (и диспергаторов), нашли множество применений в информатике .

Ссылки

• Ронен Шальтиэль, Последние разработки в экстракторах - обзор