Изменения

Перейти к: навигация, поиск

Графы-экспандеры

6 байт убрано, 01:16, 21 декабря 2017
м
Нет описания правки
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<ref>[[wikipedia:Expander_code|Wikipedia {{---}} корректирующие коды]]</ref>, экстракторах, генераторах псевдослучайных чисел<ref>[[wikipedia:Pseudorandom_number_generator|Wikipedia {{---}} генератор псевдослучайных чисел]]</ref>, сетях сортировки<ref>[[wikipedia:Sorting_network|Wikipedia {{---}} Сеть сортировки]]</ref> и компьютерных сетях<ref>[[wikipedia:Computer_network|Wikipedia {{---}} компьютерные сети]]</ref>. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как ''SL''<ref>[[wikipedia:SL_(complexity)|Wikipedia {{---}} SL complexity]]</ref>=''L''<ref>[Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291]</ref> и Теорема PCP<ref>[Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — Т. 54, вып. 3. — С. 12. — DOI:10.1145/1236457.1236459]</ref>. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d</tex>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\tfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
===Блуждания по экспандеру===
Согласно границе Чернова<ref>[[wikipedia:Chernoff_bound|Wikipedia {{---}} граница Чернова]]</ref>, если выбирать много независимых случайных значений из интервала <tex>[-1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к [[Математическое ожидание случайной величины|математическому ожиданию]] случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди<ref>[M. Ajtai,J. Komlós,E. Szemerédi Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. — 1987. — С. 132–140. — ISBN 0-89791-221-7. — DOI:10.1145/28395.28410]</ref> и Гилмана<ref>[D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 4,. — С. 1203–1220. — DOI:10.1137/S0097539794268765]</ref>, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации<ref>[[wikipedia:Randomized_algorithm|Wikipedia {{---}} теория дерандомизации]]</ref>, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
== См. также ==
92
правки

Навигация