Limites inferiores para comunicação multipartidária não determinística

Esta é uma continuação da minha pergunta anterior sobre limites inferiores de comunicação para funções booleanas parciais .

Alguém pode sugerir alguma referência nos limites inferiores para comunicação multipartidária não determinística? Venho pesquisando os artigos em campo, mas todo mundo parece mostrar separações do seguinte tipo: um limite inferior para o protocolo aleatório e um limite superior (menor) para um protocolo não determinístico. Veja, por exemplo, David, Pitassi e Viola 2009 , Gavinsky e Sherstov 2010 , Beame, David, Pitassi e Woelfel 2010 .

Especificamente, eu gostaria de saber se existe uma norma (eg para k partes) que limites inferiores de comunicação multipartidária nondeterministic tanto no número-in-the-testa ou modelo número-in-hand.$\gamma_k$$k$

Depois de muita leitura, encontrei o seguinte artigo

Troy Lee e Adi Shraibman. A desarticulação é difícil no modelo de número de participantes na testa com várias partes . Nos Anais da 23ª Conferência Anual da IEEE sobre Complexidade Computacional . 22-26 de junho de 2008.

$\mu_\alpha$

$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$

Então, eles fazem a seguinte observação.

$\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$

Existe outra norma mais forte que a discrepância que pode ser usada para limites inferiores na comunicação multipartidária não determinística? Ou é apertado? Esses resultados são muito recentes, então talvez esse seja um problema em aberto. O seguimento desta pergunta está aqui .