Проблема Гэпа-Хэмминга - Википедия - Gap-Hamming problem

В сложность коммуникации, то проблема Гэп-Хэмминга спрашивает, если Алиса и Боб каждому дается (потенциально разная) строка, каково минимальное количество битов, которые им нужно обменять, чтобы Алиса могла приблизительно вычислить Расстояние Хэмминга между их струн. В решении проблемы примерно указано, что если Алисе и Бобу дана строка, то любой протокол связи используется для вычисления расстояния Хэмминга между их строками (асимптотически) не лучше, чем Боб, отправляющий всю свою строку Алисе. Более конкретно, если Алисе и Бобу даны ${ 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]

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