Тестирование на позитивность вместо равенства

Алиса и Боб имеют n-битные строки и хотят выяснить, равны ли они при небольшом общении. Стандартным рандомизированным решением является обработка n-битных строк как полиномов степени $n$ а затем оценка полиномов по нескольким случайно выбранным элементам из поля размером больше $n$ . Это требует $O(\log |F|)$ связи.

Предположим вместо этого, что мы фиксируем лексикографический порядок строк и хотим вместо этого определить, какая строка «больше», что эквивалентно нахождению самого левого бита, где строки различаются.

Существует ли подобный рандомизированный протокол для этого или известная нижняя граница? Похоже, это относится к проверке положительности полиномов.

ps. Хотя лексикографический порядок кажется наиболее очевидным, я согласен с другими порядками: для интересующей меня цели нам нужен только какой-то порядок.

communication-complexity property-testing Суреш Венкат
источник

Я думал, что стандартным рандомизированным решением было выбрать случайную линейную комбинацию битов и просто отправить результирующую четность, что требует только

связи?

O (1)

$O(1)$

Джошуа Грохов

@ JoshuaGrochow Я думаю, что это зависит от характера случайности - публичной или частной. Протокол, который вы упоминаете, использует публичную случайность.

Сашо Николов

Для сравнения, возможно, стоит упомянуть, что детерминированная сложность равна

, поэтому тривиальный протокол является оптимальным. Это дает хороший экспоненциальный разрыв между детерминированными / точными и рандомизированными решениями, показывая, что (по крайней мере в сложности коммуникации) случайность действительно может помочь.

n + 1

$n+1$

Андрас Саламон

эм ... да.

$\:$ Сколько связи необходимо для алгоритма, который никогда не дает неправильного ответа и, для всех входных пар, МОЖЕТ дать этой входной паре с вероятностью не более 1/2?

Возможно, стоит упомянуть, что сложность связи по

окружению больше, чем, в частности,

т. Е. Она линейна для

, см. Arxiv.org/abs/cs/0309033 . Это хорошая статья :)

k

$k$

Ω (n^{1 / k} k^{- 2})

$\Omega(n^{1/k}k^{-2})$

k = 1

$k=1$

Марк Бери

Ответы:

Это известно как проблема Большего, чем сложность связи. Существует алгоритм со сложностью связи (упражнение 3.18 в книге Нисана-Кушилевича). $O(\log n)$

Изменить: Алгоритм из-за Нисана (стр. 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

Он использует подход, предложенный @Sasho Nikolov ниже - запуск двоичного поиска с использованием тестов на равенство с постоянной ошибкой для сравнения. Это можно сделать с помощью запросов, используя «шумный алгоритм двоичного поиска» Фейге, Пелега, Рагхавана и Упфаля: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf $O(\log n)$

Чтобы получить (неявный) протокол частной случайности, можно применить результат Ньюмана: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf

Григорий Ярославцев
источник

Одно простое решение для связи с полилогами - использовать равенство для двоичного поиска первого бита, где строки различаются. Решение

имеет открытую случайность: снова используйте равенство как оракула, но выполняйте каждый тест на равенство с постоянной вероятностью ошибки, чтобы каждый вызов равенства использовал

битов; теперь простого бинарного поиска не достаточно, вам нужен «шумный бинарный поиск», но есть способы сделать это со сложностью журнала

\log n

$\log n$

O (1)

$O(1)$

Сашо Николов

Не уверен, что такое «шумный бинарный поиск», но вы можете выполнить

в публичной модели случайности, выполнив бинарный поиск с использованием тестов на равенство с вероятностью ошибки

, для которых требуется

обмен данными за тест, и вы получите постоянную вероятность ошибки в целом за счет объединения.

O (\log n \log \log n)

$O(\log n \log \log n)$

O (1 / \log n)

$O(1 / \log n)$

O (\log \log n)

$O(\log \log n)$

Григорий Ярославцев

@SashoNikolov Хорошо, я думаю, что-то подобное можно использовать как «шумный бинарный поиск», который допускает постоянную долю ошибок, так что мы можем использовать постоянную вероятность ошибки в тестах на равенство: dl.acm.org/citation.cfm? id = 167129

Григорий Ярославцев

правда. Я имел в виду бинарный поиск, где каждое сравнение может давать неправильный результат с небольшой постоянной вероятностью. Я думаю, что эта статья дает необходимый результат, например: dl.acm.org/citation.cfm?id=100230

Сашо Николов

Переместил обсуждение в ответ.

Григорий Ярославцев

См . Коммуникационная сложность сложения .

$O(\log n)$

Manu
источник