갭 해밍 문제

통신 복잡성에서 갭 해밍 문제는 앨리스와 밥에게 각각 (잠재적으로 다른) 문자열이 주어진다면 앨리스가 문자열 사이의 해밍 거리를 대략 계산하기 위해 교환해야 하는 최소 비트 수는 얼마인가를 묻는다.문제의 해결책은 대략 앨리스와 밥에게 각각 끈이 주어진다면, 그들의 끈 사이의 해밍 거리를 계산하는 데 사용되는 어떤 통신 프로토콜도 밥이 그의 모든 끈을 앨리스에게 보내는 것과 다를 바 없다고 말한다.구체적으로는 앨리스와 밥에게 $각각{\displaystyle }$ n ${\displaystyle n}$ -bit$$ 문자열이 주어진 경우, 앨리스가$$$\Omega {\displaystyle \mathrm{}(n}$) ${\displaystyle \pm$${\sqrt$${n}}}$ 내에서 ${\displaystyle 문자열\sqrt{}}$ 사이의 해밍 거리를 계산하도록$$ 하는 통신 프로토콜이 존재하지 않는다.

갭 해밍 문제는 모멘트 주파수 추정과^[1] 엔트로피 추정을 포함한 많은 스트리밍 알고리즘에 대해 하한을 증명하는 응용 프로그램이 있다.^[2]

형식명세서

이 문제에서 앨리스와 밥은 각각 $x{\displaystyle \in \{}$± $}$의 문자열({\$pm{\displaystyle }$ 1$\}^{n})$과 y${\displaystyle \in \{}$ ± ${\displaystyle 1{}^{}}$$$${\displaystyle n^{}}$ ${\$ $y$$\in \{\pm$ 1$\}^{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}}}$

가능한 최소의 통신량을 사용하는 것.여기서 $\ast {\displaystyle }$ ${\displaystyle *}$은$({\displaystyle }$는) ± ${\displaystyle 1}$ ${\displaystyle \pm 1}$ 중 하나를 앨리스가 반환할 수 있음을 나타내고$$$$, $D{\displaystyle {}_{}}$ H${\displaystyle {}_{}{x}_{}}$ ,${\displaystyle y}$ )${\displaystyle$ $D_$${H}(x$$,y$$)}$은(는) x ${\$$displaystysty$ y$}$ 사이의$$ 해밍 거리$.$ 즉, 앨리스는 밥의 문자열이 유의하게 비슷한지 여부를 반환해야 한다.그녀가 밥과 교환하는 비트 수를 최소화하면서 그녀와는 아주 다르다.

문제의 해결책은 ${\displaystyle \mathrm{GHD}}$ ${\displaystyle \operatorname {GHD}을($를) 계산하는 데 적어도 $\Omega {\displaystyle \mathrm{}(n}$)$${\$displaystyle \Oomega(n)}$ 통신이$$ 필요하다고$$ 명시하고 있다.특히,${\displaystyle }$$\Omega {\displaystyle }$${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle x}$과 y ${\displaystyle y}$을(를) ${\displaystyle \{\pm 1{}^n}$ ${\$ 1$\}^{n$에서 임의로 선택해도 Ω (n ) ${\displaystystyle \Oome$ ($n)})$ 통신이$$ 필요하다.

역사

갭 해밍 문제는 원래 인디크와 우드러프에 의해 제안되었는데, 그는 처음에 문제의 단방향 통신 복잡성에 대해 선형 하한을 증명했고(앨리스가 밥으로부터만 데이터를 수신할 수 있는 경우) 일반 사례에서 선형 하한을 추측했다.^[3](앨리스와 밥이 원하는 만큼 많은 메시지를 교환할 수 있는) 무한원 사례의 문제는 차크라바티와 레게프가 반농도 논증을 통해 일반 문제 역시 선형 하한 복잡성을 가지고 있다는 것을 증명할 때까지 열려 있었고, 따라서 원문제는 완전히 해결되었다.^[4]이 결과는 처음에는 비딕이^[5], 나중에는 셰르스토프가,^[6] 최근에는 하다르, 류, 폴리안스키, 샤이비츠가 정보이론적 접근법으로 원하는 하한선을 증명하기 위한 새로운 접근법을 단순화하거나 찾으려 했던 일련의 다른 논문들이 뒤따랐다.^[7]

참조