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

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

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

Официальное заявление [ править ]

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

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

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

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

История [ править ]

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

Ссылки [ править ]