Complexidade da comunicação para decidir a associatividade

Let { 0 , . . . , N - 1 } e ∘ : S × S → S . Eu quero calcular a complexidade da comunicação para decidir se ∘ é associativo.$S=$$0,...,n-1$$\circ : S \times S \rightarrow S$$\circ$

O modelo é o seguinte. é dada como uma matriz M . Alice (resp. Bob) recebe metade das entradas da matriz aleatoriamente (o mesmo para Bob). Quero calcular o número do pior caso de entradas que Alice deve enviar para Bob para que Bob possa decidir sobre a associatividade de ∘ .$\circ$$M$$\circ$

Na verdade, é simples para reduzir o problema de decidir a igualdade de dois cordões de tamanho bit para o problema de decidir a associatividade de ∘ sobre S . Isso significa que a complexidade da comunicação da associatividade é mais baixa delimitada por Ω ( n ) . No entanto, suspeito que esse LB não seja rígido. Sendo definido em uma entrada do tamanho n 2 , eu preferiria encontrar uma complexidade de comunicação de Ω ( n 2 ) .$\Omega(n)$$\circ$$S$$\Omega(n)$$n^{2}$$\Omega(n^{2})$

Existe um resultado conhecido sobre esse problema? A resposta é por um motivo óbvio que não estou vendo?$n^{2}$

$n^{n^2}$$S$$n$$f(t)$