Complejidad de comunicación para decidir asociatividad

Sea { 0 , . . . , N - 1 } y ∘ : S × S → S . Quiero calcular la complejidad de la comunicación al decidir si ∘ es asociativo.$S=$$0,...,n-1$$\circ : S \times S \rightarrow S$$\circ$

El modelo es el siguiente. se da como una matriz M . Alice (resp. Bob) recibe la mitad de las entradas de la matriz al azar (lo mismo para Bob). Quiero calcular el número de entradas en el peor de los casos que Alice debe enviar a Bob para que Bob pueda decidir sobre la asociatividad de ∘ .$\circ$$M$$\circ$

De hecho, es simple para reducir el problema de decidir la igualdad de las dos cadenas de bits de tamaño para el problema de decidir la asociatividad de ∘ sobre S . Esto significa que la complejidad de la comunicación de la asociatividad está limitada por Ω ( n ) . Sin embargo, sospecho que este LB no es ajustado. Al estar definido en una entrada de tamaño n 2 , hubiera preferido encontrar una complejidad de comunicación de Ω ( n 2 ) .$\Omega(n)$$\circ$$S$$\Omega(n)$$n^{2}$$\Omega(n^{2})$

¿Hay un resultado conocido en este problema? ¿La respuesta es por una razón obvia que no estoy viendo?$n^{2}$

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