제품 유통을 위한 커뮤니케이션 복잡성

Question

일반적으로 길이 n의 입력에 대한 (양자) 집합 분리 문제의 경우 당사자가 통신해야 한다는 것을 알고 있습니다. $\오메가(n)$.놀랍게도 오늘 나는 이것이 제품 배포에는 해당되지 않는다는 것을 발견했습니다(제가 올바르게 이해했다면).Alice와 Bob의 입력이 임의의 분포와 독립적으로 선택되는 경우!이에 종이, 예를 들어, 통신 복잡성의 상한선을 제공합니다. $\mathcal{O}(\sqrt{n}\log(1/\epsilon))$, 어디 $\엡실론$ 여기 질문과 관련이 없는 오류 용어입니다.이제 나는 잘 알려진 다른 통신 복잡성 문제에 대한 격차가 존재하는지 궁금합니다.

질문: 임의의 입력 분포와 제품 분포를 고려할 때 의사소통 복잡성 사이에 격차가 나타나는 다른 잘 알려진 문제는 무엇입니까?내적이나 교차점에 대해서도 비슷한 결과가 있습니까?

Answer 1

집합 분리성에 대한 하드 배포는 제품 배포와는 거리가 멀기 때문에 집합 분리는 제품 배포에 더 쉽습니다.하드 배포에서 필요한 것은 무엇입니까? $(X,Y)$ 내부 제품용?우리는 각각을 원한다 $X,Y$ 별도로 매우 무작위로 설정해야 하며 우리는 $X\cdot Y$ 대부분 0이 될 것 $X \cdot Y$ 최대 1개를 포함합니다. $1$.이는 제품 배포로는 달성할 수 없습니다.당신이 얻을 수 있는 동안 $X \cdot Y$ 이는 두 입력 각각이 매우 편향되어 있음을 의미합니다.반대로, 입력이 $X,Y$ 그렇다면 아주 무작위적이죠 $X \cdot Y$ 많을 것이다 $1$에스.

내부 제품 기능에는 동일한 문제가 발생하지 않습니다.실제로 가장 어려운 분포는 균일 분포인 것 같습니다.불일치 방법을 사용하여 선형 하한을 증명할 수 있습니다. 이는 표준이며 불일치에 대한 한계를 사용합니다. 린지의 정리.

Sherstov는 그의 논문에서 최적의 간격 예시를 제시했습니다. 제품 및 비제품 배포에서의 통신 복잡성.그의 기능은 큰 단색이 없도록 선택된 무작위 기능입니다. $1$-직사각형.최종 결과는 무작위 통신 복잡성이 다음과 같은 함수입니다. $\오메가(n)$, 그러나 모든 제품 배포의 경우 무작위 통신 복잡성은 다음과 같습니다. $O(1)$.