Kompleksitas komunikasi mendekati ukuran persimpangan set

8

Pertimbangkan masalah set-persimpangan: Alice dan Bob masing-masing mendapatkan subset dari {1,,n} , dan mereka ingin tahu apakah set mereka berpotongan. Ini adalah masalah kanonik dari kompleksitas komunikasi, dan diketahui bahwa protokol acak untuk masalah ini memerlukan Θ(n) bit komunikasi ( lihat survei di sini ). Dalam kasus di mana set berukuran k untuk kn , diketahui bahwa protokol acak membutuhkan Θ(k) bit ( lihat di sini ).

Pertimbangkan sekarang varian di mana Alice dan Bob ingin tahu ukuran persimpangan set mereka. Jelas, menghitung ukuran yang tepat akan mengurangi masalah set-persimpangan standar, dan ini berlaku bahkan jika mereka hanya ingin menghitung perkiraan multiplikasi ukuran. Namun, apa yang terjadi jika mereka ingin menghitung perkiraan tambahan ukuran persimpangan? Apakah ada batas bawah atau batas atas yang diketahui tentang masalah ini?

Saya sangat tertarik dengan pertanyaan ini dalam pengaturan set kecil, yaitu, kasus di mana set adalah ukuran kn .

Atau Meir
sumber
1
Aditif c-aproksimasi perpotongan dari dua (n * 2 * c) -bit set setidaknya sekeras komputasi persimpangan dua set n-bit; kita mengurangi dari yang terakhir ke yang sebelumnya dengan menyalin setiap bit 2c kali dan membulatkan ukuran persimpangan ke kelipatan terdekat dari c.
daniello
1
Saya kira pengurangan berikut dari disjointness set klasik ke additive perkiraan akan memberi Anda batas bawah. Misalkan ada protokol yang mencapai pendekatan α = f ( n ) . Mereka pemain menduplikasi masing-masing n bit asli ke 3 f ( n ) bit. Karenanya jika tidak ada persimpangan, output paling banyak adalah f ( n ) , dan jika ada persimpangan, paling tidak 2 f ( n ) . Ini memberi batas bawah Ω ( nαα=f(n)n3f(n)f(n)2f(n). Ω(n3f(n))
Sajin Koroth
Terima kasih! Jika Anda mengubah komentar Anda menjadi jawaban, saya akan menerimanya.
Atau Meir
1
Jangan dua himpunan bagian dari ukuran n selalu berpotongan? {1,,n}n
Geoffrey Irving

Jawaban:

4

Saya akan memberikan dua batas atas. Biarkan dan B menjadi set yang diberikan masing-masing untuk Alice dan Bob, dan beri a = | A | , b = | B | , c = | A B | .ABa=|A|b=|B|c=|AB|

Pertama, ada protokol acak yang, diberikan dan ϵ > 0 , menghitung dengan probabilitas 1 - ϵ perkiraan c hingga kesalahan aditif d , menggunakan O ( ( min { a , b }d>0ϵ>01ϵcdbit komunikasi, danO((min{a,b}O((min{a,b}d)2lognlogϵ1)bit keacakan.O((min{a,b}d)2logmin{a,b}logϵ1)

Protokolnya sebagai berikut:

  1. Jika , pihak yang melihatnya mengakhiri protokol dan menghasilkan 0 sebagai estimasi. Jika tidak, Alice dan Bob berkomunikasi a dan b satu sama lain, dan menentukan mana yang lebih kecil. Aku akan menganggap di bawah wlog bahwa sebuah b .dmin{a,b}0abab

  2. Alice menggambar sampel acak seragam independen a iA , i < t , dan mengirimkannya ke Bob.t=log(2ϵ1)a2/(2d2)aiAi<t

  3. Bob memperkirakan sebagai ac.at|{i<t:aiB}|

Protokol adalah benar dengan batas-batas Chernoff-Hoeffding: jika menunjukkan indikator variabel acak acara yang sayaB , maka X i , i < t , adalah variabel iid dengan mean p = c / a . Jadi, Pr [ a ¯ Xc - d ] = Pr [ ¯ Xp - dXiaiBXii<tp=c/a dan juga untukPr[a ¯ Xc+d].

Pr[aX¯cd]=Pr[X¯pda]exp(2(da)2t)ϵ2,
Pr[aX¯c+d]

Sekarang, batas-batas ini agak boros jika : ada juga varian Chernoff batas yang menyatakan Pr [ ¯ Xp - δ ]ca yang akan memungkinkan kita untuk mendapatkan dengan jumlah sampeltlebih kecil dengan faktor sekitarp. Masalahnya adalah bahwap=c/aadalah jumlah yang ingin kita perkirakan, maka kita tidak mengetahuinya sebelumnya. Ini dapat diatasi dengan membuat estimasi pertama ball-parkc.

Pr[X¯pδ]exp(δ22pt),Pr[X¯p+δ]exp(δ23pt),δp,
tpp=c/ac

Jadi, protokol yang ditingkatkan menghitung dengan probabilitas suatu aditif d -pendekatan c menggunakan O ( min { a , b }1ϵdcbit komunikasi, danO(min{a,b}O(min{a,b}d(1+cd)lognlogϵ1)bit keacakan, dan itu berjalan sebagai berikut (konstanta tidak dioptimalkan):O(min{a,b}d(1+cd)logmin{a,b}logϵ1)

  1. Sama seperti di atas.

  2. Alice menarik sampel acak a / d dari A , dan mengirimkannya ke Bob.r=10(logϵ1)a/dA

  3. Bob jumlah berapa banyak sampel ini milik , dan mengirimkan nomor ini, s , untuk Alice.Bs

  4. Jika , protokol berakhir dengan output 0 .as/rd/20

  5. Alice menarik sampel acak yang sayaA , i < t , dan mengirimkannya ke Bob.t=10sa/daiAi<t

  6. Bob memperkirakan sebagai ac.at|{i<t:aiB}|

Tanpa masuk ke dalam perincian, batas Chernoff yang dikutip di atas menyiratkan bahwa dengan probabilitas tinggi, nilai adalah Θ ( c / a ) , dalam hal ini protokol tidak melebihi biaya yang dinyatakan, dan ia menghitung dengan probabilitas tinggi a. Estimasi C yang baik dengan aplikasi lain dari batas Chernoff.s/rΘ(c/a)c

Emil Jeřábek
sumber
Terima kasih atas jawaban bermanfaatnya! Namun, saya baru sadar saya lupa menyebutkan bahwa saya lebih tertarik pada kasus di mana set kecil dibandingkan dengan . Apakah ada cara untuk membuat protokol Anda berfungsi dalam pengaturan ini? Maaf atas kebingungan ...n
Atau Meir
Apa yang Anda maksud dengan perkiraan aditif dalam pengaturan seperti itu?
Emil Jeřábek
Saya akan tertarik pada pendekatan hingga istilah aditif yang bermakna, mulai dari yang konstan hingga linier dalam ukuran set.
Atau Meir
Tetapi kesalahan hingga fraksi konstan ukuran himpunan adalah sama dengan perkiraan multiplikatif, bukan?
Emil Jeřábek
Oh saya mengerti, Anda membiarkan sebagian kecil dari ukuran dua set aslinya, bahkan jika persimpangan jauh lebih kecil.
Emil Jeřábek
3

[Jawaban Emil jelas lebih baik dan lebih sederhana jika Anda tertarik pada jenis kesalahan ini, kecuali karena alasan tertentu Anda membutuhkan protokol Anda untuk menjadi deterministik. Ups.]

Ada protokol nontrivial jika Anda tertarik pada perkiraan aditif tipe untuk konstanta kecil δ > 0 .±δnδ>0

Sebagai contoh, ini satu:

  1. nnn
  2. (k,ε)O~(n)O~ε(n)n
  3. (S1A,S2A)(S1B,S2B)
    max{min{|S1AS1B|,|S2AS2B|},min{|S1AS2B|,|S2AS1B|}}
    δ>0±δnδk,ε. Persimpangan antara item yang tersisa dapat diperkirakan dengan dekat dengan metode statistik standar, karena grafik antara set ini mematuhi statistik dari grafik bipartit acak dengan kerapatan yang diberikan.

Jika pendekatan semacam ini menarik bagi Anda, Anda mungkin mendapatkan jarak tempuh lebih banyak dari lemma keteraturan grafik lainnya, terutama Frieze-Kannan. Ini adalah survei.

GMB
sumber
Terima kasih! Koneksi ke partisi keteraturan menarik.
Atau Meir