Dolne granice niedeterministycznej komunikacji wielostronnej

Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich .

Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla protokołu niedeterministycznego. Patrz na przykład David, Pitassi i Viola 2009 , Gavinsky and Sherstov 2010 , Beame, David, Pitassi i Woelfel 2010 .

W szczególności chciałbym wiedzieć, czy istnieje norma (np. dla stron), która w dolnym zakresie ogranicza niedeterministyczną komunikację wielopartyjną w modelu numer na czole lub numer na ręce.$\gamma_k$$k$

Po wielu lekturach znalazłem następujący artykuł

Troy Lee i Adi Shraibman. Rozłączenie jest trudne w modelu wielopartyjnym numer na czole . W materiałach 23 dorocznej konferencji IEEE na temat złożoności obliczeniowej . 22-26 czerwca 2008 r.

Autorzy pokazują, że losowa komunikacja z błędem ograniczonym jest dolna ograniczona przybliżoną normą przecięcia walca (por. Definicja 5 w pracy).$\mu_\alpha$

Twierdzenie 6: Niech M będzie znakiem tensorem, a . Następnie gdzie i .0 ≤ ε < 1 / 2 R k ε ( M ) ≥ log ( ľ a- ( M ) ) - log ( a- ε ) a- ε = 1 / ( 1 - 2 ε ) a- ≥ a- $k$$0\leq \epsilon<1/2$$R_\epsilon^k(M)\geq \log(\mu^\alpha(M))-\log(\alpha_\epsilon)$$\alpha_\epsilon=1/(1-2\epsilon)$$\alpha\geq\alpha_\epsilon$

Następnie robią następującą uwagę.

Uwaga 7: Miło jest zauważyć, że ponieważ protokół niedeterministyczny indukuje pokrycie tensora przecięciami walca, wynika z tego, że jest dolną granicą niedeterministycznej złożoności komunikacji.$\log\mu^\infty$

$\alpha\to\infty$$M$$\mu^\infty(M)=1/Disc(M)$$Disc(M)$$M$$k$$\Omega(\log n/(k-1))$$\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$$\mu^\alpha$

Czy istnieje jakakolwiek inna norma silniejsza niż rozbieżność, która może być stosowana w przypadku niższych granic w niedeterministycznej komunikacji wielopartyjnej? Czy jest ciasno? Te wyniki są bardzo aktualne, więc może to jest otwarty problem. Kontynuacja tego pytania jest tutaj .