Проблема Гэпа-Хэмминга

Что касается сложности связи , проблема Хэмминга с пробелом спрашивает: если Алисе и Бобу дана каждая (потенциально разная) строка, каково минимальное количество битов, которыми им необходимо обменяться, чтобы Алиса приблизительно вычислила расстояние Хэмминга между их строками? . Решение проблемы примерно гласит, что если Алисе и Бобу дана строка, то любой протокол связи , используемый для вычисления расстояния Хэмминга между их строками, работает (асимптотически) не лучше, чем Боб, отправляющий всю свою строку Алисе. Точнее, если Алисе и Бобу даны $n$ -битовых строк, не существует протокола связи, который позволил бы Алисе вычислить расстояние Хэмминга между их строками с точностью до $\pm {\sqrt {n}}$ используя менее $\Omega (n)$ биты .

Проблема пробела-Хемминга применяется для доказательства нижних границ для многих алгоритмов потоковой передачи, включая оценку моментной частоты. ^[1] и оценка энтропии. ^[2]

Официальное заявление

В этой задаче Алиса и Боб получают по строке: $x\in \{\pm 1\}^{n}$ и $y\in \{\pm 1\}^{n}$ соответственно, в то время как Алисе требуется вычислить (частичную) функцию,

\operatorname {GHD} (x,y)={\begin{cases}+1&D_{H}(x,y)\geq {\frac {n}{2}}+{\sqrt {n}}\\-1&D_{H}(x,y)\leq {\frac {n}{2}}-{\sqrt {n}}\\*&{\text{otherwise}},\end{cases}}

используя как можно меньше возможностей общения. Здесь, $*$ указывает, что Алиса может вернуть любой из $\pm 1$ и $D_{H}(x,y)$ Хэмминга расстояние между $x$ и $y$ . Другими словами, Алисе необходимо узнать, существенно ли строка Боба похожа или существенно отличается от ее, при этом минимизируя количество битов, которыми она обменивается с Бобом.

Решение проблемы гласит, что вычисление $\operatorname {GHD}$ требуется как минимум $\Omega (n)$ коммуникация. В частности, это требует $\Omega (n)$ общение, даже когда $x$ и $y$ выбираются равномерно случайным образом из $\{\pm 1\}^{n}$ .

История

Проблема Гэпа-Хэмминга была первоначально предложена Индиком и Вудраффом в начале 2000-х годов, которые первоначально доказали линейную нижнюю границу сложности односторонней связи (где Алисе разрешено получать данные только от Боба) и предположили линейную нижняя граница в общем случае. ^[3] Вопрос о случае бесконечного раунда (в котором Алисе и Бобу разрешено обмениваться любым количеством сообщений) оставался открытым до тех пор, пока Чакрабарти и Регев не доказали с помощью аргумента против концентрации , что общая проблема также имеет линейную нижнюю границу сложности. тем самым полностью решая первоначальный вопрос. ^[4] За этим результатом последовала серия других статей, в которых стремились упростить или найти новые подходы к доказательству желаемой нижней оценки, в частности, первая из них была написана Видиком. ^[5] and later by Sherstov, ^[6] и, недавно, с теоретико-информационным подходом Хадара, Лю, Полянского и Шаевица. ^[7]

Ссылки

^ Индик, Петр; Вудрафф, Дэвид (2005). «Оптимальные аппроксимации частотных моментов потоков данных». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 . п. 202. дои : 10.1145/1060590.1060621 . ISBN 9781581139600 . S2CID 7911758 .
^ Чакрабарти, Амит; Кормод, Грэм; Макгрегор, Эндрю (2010). «Почти оптимальный алгоритм оценки энтропии потока». Транзакции ACM на алгоритмах . 6 (3): 1–21. CiteSeerX 10.1.1.190.5419 . дои : 10.1145/1798596.1798604 . ISSN 1549-6325 . S2CID 6733816 .
^ Индик, П.; Вудрафф, Д. (2003). «Точные нижние оценки для задачи о различных элементах». 44-й ежегодный симпозиум IEEE по основам информатики, 2003 г. Материалы . стр. 283–288. дои : 10.1109/SFCS.2003.1238202 . ISBN 9780769520407 . S2CID 7648045 .
^ Чакрабарти, Амит; Регев, Одед (2011). «Оптимальная нижняя граница сложности связи на расстоянии разрыва». Материалы 43-го ежегодного симпозиума ACM по теории вычислений - STOC '11 . п. 51. arXiv : 1009.3460 . дои : 10.1145/1993636.1993644 . ISBN 9781450306911 . S2CID 10274326 .
^ Видик, Томас (2012). «Неравенство концентрации для перекрытия вектора на большом множестве с применением к коммуникационной сложности проблемы расстояния Хэмминга» . Чикагский журнал теоретической информатики . 18 : 1–12. дои : 10.4086/cjtcs.2012.001 .
^ Шерстов, Александр А. (17 мая 2012 г.). «Коммуникационная сложность расстояния Хэмминга» . Теория вычислений . 8 (1): 197–208. дои : 10.4086/toc.2012.v008a008 . ISSN 1557-2862 .
^ Шаевиц, Офер; Полянский, Юрий; Лю, Цзинбо; Хадар, Ури (25 января 2019 г.). «Коммуникационная сложность оценки корреляций». arXiv : 1901.09100v2 [ cs.IT ].

[:0-1] Индик, Петр; Вудрафф, Дэвид (2005). «Оптимальные аппроксимации частотных моментов потоков данных». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 . п. 202. дои : 10.1145/1060590.1060621 . ISBN 9781581139600 . S2CID 7911758 .

[2] Чакрабарти, Амит; Кормод, Грэм; Макгрегор, Эндрю (2010). «Почти оптимальный алгоритм оценки энтропии потока». Транзакции ACM на алгоритмах . 6 (3): 1–21. CiteSeerX 10.1.1.190.5419 . дои : 10.1145/1798596.1798604 . ISSN 1549-6325 . S2CID 6733816 .

[3] Индик, П.; Вудрафф, Д. (2003). «Точные нижние оценки для задачи о различных элементах». 44-й ежегодный симпозиум IEEE по основам информатики, 2003 г. Материалы . стр. 283–288. дои : 10.1109/SFCS.2003.1238202 . ISBN 9780769520407 . S2CID 7648045 .

[4] Чакрабарти, Амит; Регев, Одед (2011). «Оптимальная нижняя граница сложности связи на расстоянии разрыва». Материалы 43-го ежегодного симпозиума ACM по теории вычислений - STOC '11 . п. 51. arXiv : 1009.3460 . дои : 10.1145/1993636.1993644 . ISBN 9781450306911 . S2CID 10274326 .

[5] Видик, Томас (2012). «Неравенство концентрации для перекрытия вектора на большом множестве с применением к коммуникационной сложности проблемы расстояния Хэмминга» . Чикагский журнал теоретической информатики . 18 : 1–12. дои : 10.4086/cjtcs.2012.001 .

[6] Шерстов, Александр А. (17 мая 2012 г.). «Коммуникационная сложность расстояния Хэмминга» . Теория вычислений . 8 (1): 197–208. дои : 10.4086/toc.2012.v008a008 . ISSN 1557-2862 .

[7] Шаевиц, Офер; Полянский, Юрий; Лю, Цзинбо; Хадар, Ури (25 января 2019 г.). «Коммуникационная сложность оценки корреляций». arXiv : 1901.09100v2 [ cs.IT ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]