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

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

А диспергатор связанный граф.

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

${displaystyle E: [N] imes [D] ightarrow [M]}$

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

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

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

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

Рекомендации

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