Testowanie pozytywności zamiast równości

Alice i Bob mają n-bitowe ciągi i chcą dowiedzieć się, czy są równe, podczas niewielkiej komunikacji. Standardowe rozwiązanie randomizowane polega na traktowaniu ciągów n-bitowych jako wielomianów stopnia a następnie ocenie wielomianów na kilku losowo wybranych elementach z pola o wielkości większej niż . Wymaga to komunikacji . $n$ $n$ $O(\log |F|)$

Załóżmy zamiast tego, że naprawiamy uporządkowanie leksykograficzne nad ciągami i chcemy zamiast tego ustalić, który ciąg jest „większy”, co jest równoważne znalezieniu najbardziej lewego skraju, gdzie różnią się ciągi.

Czy istnieje podobny losowy protokół do wykonania tej czynności lub znana dolna granica? Wydaje się, że odnosi się to do testowania pozytywności wielomianów.

ps Podczas leksykograficzny kolejność wydaje się najbardziej oczywiste, jestem zadowolony z innych porządków: dla celów Jestem zainteresowany, wszystko czego potrzebujemy to jakiś porządek.

communication-complexity property-testing

— Suresh Venkat
źródło

Myślałem, że standardowym rozwiązaniem losowym było wybranie losowej liniowej kombinacji bitów i po prostu wysłanie wynikowej parzystości, która wymaga tylko komunikacji

O (1)

$O(1)$

— Joshua Grochow

@JoshuaGrochow Myślę, że to zależy od natury losowości - publicznej lub prywatnej. Wspomniany protokół wykorzystuje losowość publiczną.

— Sasho Nikolov

Dla porównania warto wspomnieć, że złożoność deterministyczna wynosi

n + 1

$n+1$ , więc trywialny protokół jest optymalny. Daje to miłą wykładniczą lukę między rozwiązaniami deterministycznymi / dokładnymi a randomizowanymi, co pokazuje, że (przynajmniej w złożoności komunikacyjnej) losowość naprawdę może pomóc.

— András Salamon

o tak.

$\:$ Ile potrzeba komunikacji dla algorytmu, który nigdy nie daje złej odpowiedzi i dla wszystkich par wejściowych daje MAYBE tej parze wejściowej z prawdopodobieństwem co najwyżej 1/2?

k

$k$

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

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

k = 1

$k=1$

Odpowiedzi:

$O(\log n)$

Edycja: algorytm wynika z Nisana (strona 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

$O(\log n)$

Aby uzyskać (nieprecyzyjny) prywatny protokół losowości, można zastosować wynik Newmana: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf

— Grigorij Jarosławcew
źródło

Jednym łatwym rozwiązaniem z komunikacją polilogu jest użycie równości do binarnego wyszukiwania pierwszego bitu, w którym łańcuchy się różnią. The

\log n

$\log n$ rozwiązaniem jest losowość publiczna: ponownie użyj równości jako wyroczni, ale wykonaj każdy test równości ze stałym prawdopodobieństwem błędu, aby każde wywołanie równości wykorzystało

O (1)

$O(1)$ bity; teraz proste wyszukiwanie binarne nie wystarcza, potrzebujesz „hałaśliwego wyszukiwania binarnego”, ale są na to sposoby ze złożonością logów

— Sasho Nikolov

Nie wiem, co to jest „hałaśliwe wyszukiwanie binarne”, ale możesz to zrobić

O (\log n \log \log n)

$O(\log n \log \log n)$ w publicznym modelu losowości poprzez wyszukiwanie binarne przy użyciu testów równości z prawdopodobieństwem błędu

O (1 / \log n)

$O(1 / \log n)$ , co wymaga

O (\log \log n)

$O(\log \log n)$ komunikacji na test, a całkowite prawdopodobieństwo wystąpienia błędu jest ograniczone przez związek.

— Grigorij Jarosławcew

@SashoNikolov Ok, myślę, że coś takiego można wykorzystać jako „hałaśliwe wyszukiwanie binarne”, które toleruje stały ułamek błędów, dzięki czemu możemy użyć stałego prawdopodobieństwa błędu w testach równości: dl.acm.org/citation.cfm? id = 167129

— Grigorij Yaroslavtsev

prawdziwe. Miałem na myśli wyszukiwanie binarne, w którym każde porównanie może dać zły wynik z małym stałym prawdopodobieństwem. Myślę, że ten artykuł daje pożądany

— Sasho Nikolov

Przenieśli dyskusję do odpowiedzi.

— Grigorij Jarosławtsev

Zobacz złożoność komunikacji dodawania .

Jak wspomniał Grigory, istnieje protokół z komunikacją $O(\log n)$ . Wynika to z Nisan i Safry. Ich protokół albo używa losowości publicznej, albo nie jest jawny. Powyższy artykuł podaje taki, który wykorzystuje losowość prywatną i jest jawny (poprzez stosunkowo standardowe użycie generatorów pseudolosowych); omawia także dopasowanie dolnych granic w modelu losowości publicznej.

— Manu
źródło