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

14

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

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

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

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

Суреш Венкат
источник
1
Я думал, что стандартным рандомизированным решением было выбрать случайную линейную комбинацию битов и просто отправить результирующую четность, что требует только связи? O(1)
Джошуа Грохов
@ JoshuaGrochow Я думаю, что это зависит от характера случайности - публичной или частной. Протокол, который вы упоминаете, использует публичную случайность.
Сашо Николов
1
Для сравнения, возможно, стоит упомянуть, что детерминированная сложность равна , поэтому тривиальный протокол является оптимальным. Это дает хороший экспоненциальный разрыв между детерминированными / точными и рандомизированными решениями, показывая, что (по крайней мере в сложности коммуникации) случайность действительно может помочь. n+1
Андрас Саламон
1
эм ... да. Сколько связи необходимо для алгоритма, который никогда не дает неправильного ответа и, для всех входных пар, МОЖЕТ дать этой входной паре с вероятностью не более 1/2?
1
Возможно, стоит упомянуть, что сложность связи по окружению больше, чем, в частности, Ω ( n 1 / k k - 2 ), т. Е. Она линейна для k = 1 , см. Arxiv.org/abs/cs/0309033 . Это хорошая статья :)kΩ(n1/kk2)k=1
Марк Бери

Ответы:

11

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

Изменить: Алгоритм из-за Нисана (стр. 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О(журналN)

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

Григорий Ярославцев
источник
5
Одно простое решение для связи с полилогами - использовать равенство для двоичного поиска первого бита, где строки различаются. Решение имеет открытую случайность: снова используйте равенство как оракула, но выполняйте каждый тест на равенство с постоянной вероятностью ошибки, чтобы каждый вызов равенства использовал O ( 1 ) битов; теперь простого бинарного поиска не достаточно, вам нужен «шумный бинарный поиск», но есть способы сделать это со сложностью журналажурналNО(1)
Сашо Николов
2
Не уверен, что такое «шумный бинарный поиск», но вы можете выполнить в публичной модели случайности, выполнив бинарный поиск с использованием тестов на равенство с вероятностью ошибки O ( 1 / log n ) , для которых требуется O ( log зарегистрируйте n ) обмен данными за тест, и вы получите постоянную вероятность ошибки в целом за счет объединения. О(журналNжурналжурналN)О(1/журналN)О(журналжурналN)
Григорий Ярославцев
2
@SashoNikolov Хорошо, я думаю, что-то подобное можно использовать как «шумный бинарный поиск», который допускает постоянную долю ошибок, так что мы можем использовать постоянную вероятность ошибки в тестах на равенство: dl.acm.org/citation.cfm? id = 167129
Григорий Ярославцев
1
правда. Я имел в виду бинарный поиск, где каждое сравнение может давать неправильный результат с небольшой постоянной вероятностью. Я думаю, что эта статья дает необходимый результат, например: dl.acm.org/citation.cfm?id=100230
Сашо Николов
Переместил обсуждение в ответ.
Григорий Ярославцев