4430
правок
Поиск предков: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 84: | Строка 84: | ||
'''Нижние границы''' | '''Нижние границы''' | ||
Все нижние границы до выхода работы [15] были показаны на модели коммуникативной игры. Айтай [ ] первым представил суперконстантную нижнюю границу. Его результаты, с поправкой Милтерсена [12], показывают, что для полиномиального объема памяти существует n как функция от | Все нижние границы до выхода работы [15] были показаны на модели коммуникативной игры. Айтай [1] первым представил суперконстантную нижнюю границу. Его результаты, с поправкой Милтерсена [12], показывают, что для полиномиального объема памяти существует n как функция от <math>\ell</math>, позволяющая получить время запроса <math>\Omega(\sqrt{lg \; \ell})</math>, и аналогично существует <math>\ell</math> как функция от n, позволяющая получить сложность запроса <math>\Omega(\sqrt[3]{lg \; n})</math>. | ||
Милтерсен и другие [ ] пересмотрели доказательство Айтая, распространив его на рандомизированные алгоритмы. Что более важно, они отразили суть доказательства в лемме о независимом исключении раунда, которая служит важным инструментом при доказательстве нижних границ в асимметричной коммуникации. | Милтерсен и другие [13] пересмотрели доказательство Айтая, распространив его на рандомизированные алгоритмы. Что более важно, они отразили суть доказательства в ''лемме о независимом исключении раунда'', которая служит важным инструментом при доказательстве нижних границ в асимметричной коммуникации. | ||
Бим и Фич [ ] улучшили нижние границы Айтая до и | Бим и Фич [4] улучшили нижние границы Айтая до <math>\Omega(lg \; \ell / lg \; lg \; \ell)</math> и <math>\Omega(\sqrt{lg \; n / lg \; lg \; n})</math>, соответственно. Сен и Венкатеш [17] позже представили улучшенную лемму об исключении раунда, которая обосновывает эти нижние границы в том числе и для рандомизированных алгоритмов. | ||
Наконец, используя лемму о сжатии сообщений из работы [6] (являющемся альтернативой исключению раунда), Петрашку и Торуп [15] предложили оптимальный компромисс для коммуникативных игр. Он также является оптимальной нижней границей в других моделях, в которых S > | Наконец, используя лемму о сжатии сообщений из работы [6] (являющемся альтернативой исключению раунда), Петрашку и Торуп [15] предложили оптимальный компромисс для коммуникативных игр. Он также является оптимальной нижней границей в других моделях, в которых <math>S \ge n^{1 + \varepsilon}</math>, но не подходит для меньшего объема памяти. | ||
Что более важно, в [ ] были разработаны первые инструменты для доказательства нижних границ, превышающих коммуникационную сложность, для случаев S = | Что более важно, в [15] были разработаны первые инструменты для доказательства нижних границ, превышающих коммуникационную сложность, для случаев <math>S = n^{1 + o(1)}</math>. Здесь впервые было проведено разделение между структурой данных полиномиального размера и структурой размера, близкого к линейному. Его принципиально невозможно получить при помощи нижней границы для прямых коммуникаций, поскольку редукция к коммуникативным играм зависит только от lg S. | ||
| Строка 102: | Строка 102: | ||
С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается отклонить большую часть запросов, прежде чем приступить к зондированию. | С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается ''отклонить'' большую часть запросов, прежде чем приступить к зондированию. | ||
