Najlepsza złożoność komunikacji dolna granica rozłączności

Dobrze wiadomo, że żaden deterministyczny protokół dwupartyjny nie może rozwiązać problemu rozłączności (DISJ) na wejściach bitowych bez wysyłania n + 1 bitów w najgorszym przypadku (patrz np. Książka Kushilevitza i Nisana). W przypadku protokołów losowych z ograniczonym błędem dolną granicę δ n , dla niektórych stałych δ , pokazano również w zasadniczym artykule Razborova [Razborov92]. Moje pytanie brzmi:$n$$n+1$$\delta n$$\delta$

Jaka jest obecnie najbardziej znana wyraźna wartość (zarówno górna, jak i dolna granica)?$\delta$

Ponadto, czy istnieje przekonanie o rzeczywistej wartości ?$\delta$

[Razborov92] Alexander A. Razborov: O złożoności dystrybucyjnej rozłączności. Teoria Comput. Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M

W ostatnim artykule Braverman, Garg, Pankratov i Weinstein obliczają wartość$\delta$być dokładnie jakąś stałą około 0,4827, aż do czynników podliniowych. To ściśle wiąże się ze złożonością komunikacji rozłączności.

Sama stała została znaleziona przy użyciu komputerowego systemu algebry i, o ile wiem, nie można tego wyrazić prosto.