ギャップ・ハミング問題
コミュニケーション複雑性理論における問題

通信の複雑性において、ギャップ・ハミング問題は、アリスとボブにそれぞれ（異なる可能性のある）文字列が与えられた場合、アリスがそれらの文字列間のハミング距離を近似的に計算するために交換する必要があるビットの最小数は何かという問題です。この問題の解は、おおよそ、アリスとボブにそれぞれ文字列が与えられた場合、それらの文字列間のハミング距離を計算するために使用される通信プロトコルはどれも、ボブがアリスに文字列全体を送信するのと（漸近的に）同じ結果になる、ということです。より具体的には、アリスとボブにそれぞれ -ビットの文字列が与えられた場合、アリスがビット未満でそれらの文字列間のハミング距離を 以内で計算できる通信プロトコルは存在しません。 n {\displaystyle n} ± n {\displaystyle \pm {\sqrt {n}}} Ω （ n ） {\displaystyle \オメガ (n)}

ギャップハミング問題は、モーメント周波数推定[1]やエントロピー推定[2]など、多くのストリーミングアルゴリズムの下限値を証明することに応用されています。

正式な声明

この問題では、アリスとボブはそれぞれ文字列とを受け取り、アリスは（部分的な）関数を計算する必要がある。 × ∈ { ± 1 } n {\displaystyle x\in \{\pm 1\}^{n}} y ∈ { ± 1 } n {\displaystyle y\in \{\pm 1\}^{n}}

GHD ⁡ （ × 、 y ） ＝ { + 1 D H （ × 、 y ） ≥ n 2 + n − 1 D H （ × 、 y ） ≤ n 2 − n ∗ さもないと 、 {\displaystyle \operatorname {GHD} (x,y)={\begin{cases}+1&D_{H}(x,y)\geq {\frac {n}{2}}+{\sqrt {n}}\\-1&D_{H}(x,y)\leq {\frac {n}{2}}-{\sqrt {n}}\\*&{\text{otherwise}},\end{cases}}}

可能な限り最小限の通信で。ここで、 はアリスが のいずれかを返すことができることを示し、は と の間のハミング距離です。言い換えれば、アリスはボブと交換するビット数を最小限に抑えながら、ボブの文字列が自分の文字列と有意に類似しているか、有意に異なっているかを返す必要があります。 ∗ {\displaystyle *} ± 1 {\displaystyle \pm 1} D H （ × 、 y ） {\displaystyle D_{H}(x,y)} × {\displaystyle x} y {\displaystyle y}

この問題の解は、計算には少なくとも通信が必要であることを示しています。特に、とが から一様ランダムに選択される場合でも、通信が必要になります。 GHD {\displaystyle \operatorname {GHD} } Ω （ n ） {\displaystyle \オメガ (n)} Ω （ n ） {\displaystyle \オメガ (n)} × {\displaystyle x} y {\displaystyle y} { ± 1 } n {\displaystyle \{\pm 1\}^{n}}

歴史

ギャップ・ハミング問題は、2000年代初頭にインディクとウッドラフによって提唱されました。彼らは当初、この問題の片方向通信複雑度（アリスはボブからのみデータを受信する）の線形下限値を証明し、一般の場合にも線形下限値を推測しました。 [3]無限ラウンドの場合（アリスとボブが望むだけの数のメッセージを交換できる場合）の問題は未解決のままでしたが、チャクラバーティとレゲフが反集中論を用いて、一般の問題にも線形下限値複雑度が存在することを証明し、当初の問題は完全に解決されました。[4]この結果を受けて、望ましい下限値を証明するための簡略化や新たなアプローチを探る一連の論文が発表されました。特に、最初にヴィディック[5]、その後シェルストフ[6]、そして最近ではハダール、リュー、ポリャンスキー、シャイエヴィッツによる情報理論的アプローチが発表されました。[7]

参考文献

  1. ^ Indyk, Piotr; Woodruff, David (2005). 「データストリームの周波数モーメントの最適近似」.第37回ACMコンピューティング理論シンポジウム - STOC '05 議事録. p. 202. doi :10.1145/1060590.1060621. ISBN 9781581139600. S2CID  7911758。
  2. ^ Chakrabarti, Amit; Cormode, Graham; Mcgregor, Andrew (2010). 「ストリームのエントロピーを推定するための準最適アルゴリズム」. ACM Transactions on Algorithms . 6 (3): 1– 21. CiteSeerX 10.1.1.190.5419 . doi :10.1145/1798596.1798604. ISSN  1549-6325. S2CID  6733816. 
  3. ^ Indyk, P.; Woodruff, D. (2003). 「個別要素問題に対する厳密な下限値」.第44回IEEEコンピュータサイエンス基礎シンポジウム, 2003. Proceedings . pp.  283– 288. doi :10.1109/SFCS.2003.1238202. ISBN 9780769520407. S2CID  7648045。
  4. ^ Chakrabarti, Amit; Regev, Oded (2011). 「ギャップハミング距離の通信複雑度に関する最適な下限値」.第43回ACMコンピューティング理論シンポジウム - STOC '11 論文集. p. 51. arXiv : 1009.3460 . doi :10.1145/1993636.1993644. ISBN 9781450306911. S2CID  10274326。
  5. ^ Vidick, Thomas (2012). 「大規模集合におけるベクトルの重なりに関する集中不等式と、ギャップ・ハミング距離問題の通信複雑性への応用」シカゴ理論計算機科学ジャーナル. 18 : 1–12 . doi : 10.4086/cjtcs.2012.001 .
  6. ^ Sherstov, Alexander A. (2012-05-17). 「ギャップハミング距離の通信複雑性」.コンピューティング理論. 8 (1): 197– 208. doi : 10.4086/toc.2012.v008a008 . ISSN  1557-2862.
  7. ^ Shayevitz, Ofer; Polyanskiy, Yury; Liu, Jingbo; Hadar, Uri (2019-01-25). 「相関推定における通信複雑性」. arXiv : 1901.09100v2 [cs.IT].
「https://en.wikipedia.org/w/index.php?title=ギャップ・ハミング問題&oldid=1136771689」より取得