Masalah kompleksitas komunikasi dengan jarak linear

8

Adakah kompleksitas komunikasi acak yang diketahui (non-sepele) dengan batas bawah untuk masalah kesenjangan alami di mana 1-input secara linear jauh dari 0-input? Artinya, fungsi parsial sedemikian rupa sehingga jarak Hamming antara setiap ( x , y ) f - 1 ( 1 ) dan ( x , y ) f - 1 (f:{0,1}2n{0,1,}(x,y)f1(1) linier - dan bahwa f memerlukan protokol acak untuk berkomunikasi (katakanlah) Ω ( (x,y)f1(0)fbit?Ω(n)

(Misalnya, masalah Gap-Hamming-Distance memiliki jarak, sedangkan saya sedang mencariΩ(n)jarak; di manaGHD(x,y)=1jikaHD(x,y)n/2+2nΩ(n)GHD(x,y)=1 danGHD(x,y)=1jikaHD(x,y)n/2-HD(x,y)n/2+nGHD(x,y)=1 .)HD(x,y)n/2n

Sunting : Seperti yang ditunjukkan oleh Igor, predikat kompleksitas komunikasi dapat dibuat menjadi masalah dengan jarak linear dengan mengharuskan input dikodekan oleh kode yang baik. Yang menarik bagi saya adalah apakah ada masalah dalam literatur, di mana jarak linear terjadi secara alami (seperti jarak dalam masalah Gap-Hamming-Distance).

Anonim
sumber
Apakah sesuatu seperti Boolean Hidden Matching Problem sesuai dengan tagihan? Itu memang membutuhkan bit komunikasi (satu arah, acak), dan sepertinya ada jarak linear antaraya- dantidak ada-keadaan. Ω(n)yesno
Clement C.
(atau hampir linier, saya kira, karena input termasuk matriks pencocokan )M
Clement C.
Clement terima kasih! Justru itulah jenis masalah yang saya cari!
Anonim
Masalah lain - meskipun dalam model SMP / wasit - pada dasarnya adalah Gap-Hamming-Distance dengan kesenjangan linear dalam (meskipun input x , y memiliki ukuran n log n bukannya n ). Lihat Bavarian, Gavinsky, dan Ito '15 , lebih tepatnya Definisi 1.9 dan Teorema 1.8 (bersama dengan Fakta 1.4): kompleksitas komunikasi G a p I P n dalam model SMP dengan keacakan pribadi adalah ˜ Ω ( nx,ynlognnGapIPn. Ω~(n)
Clement C.

Jawaban:

6

Misalkan menjadi kode koreksi kesalahan dengan jarak linear. Misalkan g : { 0 , 1 } n × { 0 , 1 } n{ 0 , 1 } menjadi fungsi yang kompleksitas komunikasi acaknya besar (katakanlah, Ω ( C:{0,1}n{0,1}2ng:{0,1}n×{0,1}n{0,1}atauΩ(n)).Ω(n)Ω(n))

Tentukan menjadi fungsi parsial yang pada codeword dari output C f ( x , y ) = g ( C - 1 ( x ) , C - 1 ( y ) ) , dan hasilnya f:{0,1}2n×{0,1}2n{0,1,}Cf(x,y)=g(C1(x),C1(y))jika setidaknya salah satu dari tidak di C .x,yC

Jelasnya, kompleksitas komunikasi sama dengan kompleksitas komunikasi g , dan f memuaskan properti yang untuk setiap dua input berbeda di mana f menghasilkan 0 atau 1, jarak di antara mereka adalah linier.fgff

Igor Shinkar
sumber
Terima kasih, Igor. Sementara, tak perlu dikatakan, masalah yang Anda gambarkan memiliki jarak linear - Saya mencari masalah di mana kesenjangan terjadi secara alami (dalam GHD), daripada secara artifisial (dengan menyandikan input). Apakah ada masalah seperti itu dalam literatur?
Anonim
2

nlogn(x,M,w){0,1}2n×{0,1}n×2n×{0,1}2nMnlognyesnoΘ(n)

BHMnΩ(n)

  • [BJK04] Ziv Bar-Yossef, TS Jayram, Iordanis Kerenidis. Pemisahan eksponensial kompleksitas komunikasi satu arah klasik dan kuantum, Prosiding ACM STOC 2004
  • [KR06] Iordanis Kerenidis, Ran Raz. Kompleksitas komunikasi satu arah dari Masalah Pencocokan Tersembunyi Boolean. Kolokium Elektronik tentang Kompleksitas Komputasi (ECCC) 13 (087) (2006)
Clement C.
sumber