Problemy z komunikacją, o których nie wiadomo, że istnieje deterministyczne twierdzenie o sumie bezpośredniej

Jest to stary otwarty problem, czy bezpośrednim suma twierdzenie zachodzi dla deterministycznego złożoności komunikacyjnej, to znaczy, czy rozwiązywania niezależnych instancji problemu jest razy twardszy niż rozwiązywanie pojedynczą instancję. [FKNN95] wykazał następujące wyniki:$t$$t$

• Wynik negatywny: istnieje funkcja częściowa (z powodu [O90]), której deterministyczna złożoność komunikacji wynosi , ale obliczenie jej w niezależnych instancjach ma złożoność .t Θ ( t + log t ⋅ log n $\Theta(\log n)$$t$$\Theta(t + \log t \cdot \log n)$
• Wynik dodatni: dla każdej funkcji , jeżeli deterministyczna złożoność komunikacji f wynosi c, wówczas złożoność obliczenia f dla t niezależnych instancji wynosi co najmniej Ω ( t ⋅ ( $f$$f$$c$$f$$t$.$\Omega(t \cdot (\sqrt{c} - \log n))$

Nie znam żadnych innych ogólnych pozytywnych wyników w zakresie problemu sumy bezpośredniej. Wydaje się jednak, że w przypadku konkretnych problemów, które są zwykle brane pod uwagę w złożoności komunikacji, np. Równości lub rozłączności, znane jest twierdzenie o sumie bezpośredniej.

Moje pytanie brzmi: czy istnieją inne przykłady problemów, dla których nie wiadomo, czy zdeterminowane twierdzenie o złożoności komunikacyjnej jest w posiadaniu, czy nawet nie jest znane (oprócz funkcji [O90])?

Bibliografia:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Amortyzowana złożoność komunikacji. SIAM J. Comput. 24 (4): 736–750 (1995)

[O90] Dwie wiadomości są prawie optymalne do przekazywania informacji. Alon Orlitsky. PODC, strona 219-232. ACM, (1990)

$n$$\pi_i$$S_3$$\prod_i sgn(\pi_i)$$sgn(\pi_i)$$\pi_i$

$\Omega(n)$