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

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

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

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

В этой задаче Алиса и Боб получают по строке, и соответственно, в то время как Алисе требуется вычислить (частичную) функцию,

используя наименьшее возможное количество общения. Здесь, указывает, что Алиса может вернуть любой из и это Расстояние Хэмминга между и . Другими словами, Алисе необходимо вернуть, является ли строка Боба существенно похожей или значительно отличающейся от ее строки, при этом минимизируя количество битов, которыми она обменивается с Бобом.

Решение проблемы гласит, что вычисление требует, по крайней мере коммуникация. В частности, это требует общение, даже когда и выбираются равномерно случайным образом из .

История

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

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

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