Menguji positif bukannya kesetaraan

Alice dan Bob memiliki string n-bit, dan ingin mencari tahu apakah mereka setara saat melakukan sedikit komunikasi. Solusi acak standar adalah memperlakukan string n-bit sebagai polinomial derajat dan kemudian mengevaluasi polinomial atas beberapa elemen yang dipilih secara acak dari bidang ukuran yang lebih besar dari . Ini membutuhkan komunikasi . $n$ $n$ $O(\log |F|)$

Misalkan kita memperbaiki urutan leksikografis atas string dan ingin menentukan string mana yang "lebih besar", yang setara dengan menemukan bit paling kiri di mana string berbeda.

Apakah ada protokol acak serupa untuk melakukan ini, atau batas bawah yang diketahui? Ini tampaknya terkait dengan pengujian positif polinomial.

ps Sementara urutan leksikografis sepertinya yang paling jelas, saya baik-baik saja dengan urutan lain: untuk tujuan yang saya minati, yang kita butuhkan hanyalah beberapa urutan.

communication-complexity property-testing Suresh Venkat
sumber

Saya pikir solusi acak standar adalah untuk memilih kombinasi linear acak dari bit, dan hanya mengirim paritas yang dihasilkan, yang hanya membutuhkan

komunikasi?

O (1)

$O(1)$

Joshua Grochow

@ JoshuaGrochow Saya pikir itu tergantung pada sifat keacakan - publik atau pribadi. Protokol yang Anda sebutkan menggunakan keacakan publik.

Sasho Nikolov

Sebagai perbandingan, mungkin layak disebutkan bahwa kompleksitas deterministik adalah

, sehingga protokol sepele optimal. Ini memberikan celah eksponensial yang bagus antara solusi deterministik / tepat dan acak, menunjukkan bahwa (setidaknya dalam kompleksitas komunikasi), keacakan benar-benar dapat membantu.

n + 1

$n+1$

András Salamon

um ... ya.

$\:$ Berapa banyak komunikasi yang dibutuhkan untuk suatu algoritma yang tidak pernah memberikan jawaban yang salah dan, untuk semua pasangan input, memberikan MAYBE ke pasangan input dengan probabilitas paling banyak 1/2?

Mungkin perlu disebutkan bahwa kompleksitas komunikasi

-round lebih besar daripada

khususnya yaitu linear untuk

, lihat arxiv.org/abs/cs/0309033 . Ini makalah yang bagus :)

k

$k$

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

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

k = 1

$k=1$

Marc Bury

Jawaban:

Ini dikenal sebagai masalah Greater-Than dalam kompleksitas komunikasi. Algoritma dengan kompleksitas komunikasi (Latihan 3.18 dalam buku Nisan-Kushilevitz). $O(\log n)$

Sunting: Algoritma ini karena Nisan (halaman 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

Ini menggunakan pendekatan yang disarankan oleh @Sasho Nikolov di bawah ini --- menjalankan pencarian biner menggunakan tes kesetaraan dengan kesalahan konstan untuk melakukan perbandingan. Ini dapat dilakukan dengan kueri menggunakan "algoritma pencarian biner berisik" oleh Feige, Peleg, Raghavan, dan Upfal: $O(\log n)$ http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf

Untuk mendapatkan protokol keacakan pribadi (non-eksplisit) seseorang dapat menerapkan hasil Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf

Grigory Yaroslavtsev
sumber

\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 Ok, saya kira sesuatu seperti ini dapat digunakan sebagai "pencarian biner berisik", yang mentolerir sebagian kecil kesalahan sehingga kita dapat menggunakan probabilitas kesalahan konstan dalam tes kesetaraan: dl.acm.org/citation.cfm? id = 167129

Grigory Yaroslavtsev

benar. Maksud saya pencarian biner di mana setiap perbandingan dapat memberikan hasil yang salah dengan probabilitas konstan kecil. Saya pikir makalah ini memberikan hasil yang diperlukan, misalnya: dl.acm.org/citation.cfm?id=100230

Sasho Nikolov

Memindahkan diskusi menjadi jawabannya.

Grigory Yaroslavtsev

Lihat Kompleksitas komunikasi penambahan .

$O(\log n)$

Manu
sumber