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 ( linier - dan bahwa f memerlukan protokol acak untuk berkomunikasi (katakanlah) Ω ( √bit?
(Misalnya, masalah Gap-Hamming-Distance memiliki jarak, sedangkan saya sedang mencariΩ(n)jarak; di manaGHD(x,y)=1jikaHD(x,y)≥n/2+ √ danGHD(x,y)=1jikaHD(x,y)≤n/2- √ .)
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).
Jawaban:
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}2n g:{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,∗} C f(x,y)=g(C−1(x),C−1(y)) ∗ jika setidaknya salah satu dari tidak di C .x,y C
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.f g f f
sumber
sumber