Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative.

The model is the following. $\circ$ is given as a matrix $M$. Alice (resp. Bob) is given half the entries of the matrix at random (same for Bob). I want to compute the worst case number of entries that Alice must send to Bob so that Bob can decide on the associativity of $\circ$.

In fact, it is simple to reduce the problem of deciding the equality of two bit strings of size $\Omega(n)$ to the problem of deciding the associativity of $\circ$ over $S$. This means that the communication complexity of the associativity is lower bounded by $\Omega(n)$. However, I suspect that this LB is not tight. Being defined on an input of size $n^{2}$, I would have prefer to find a communication complexity of $\Omega(n^{2})$.

Is there a known result on this problem ? Is the answer is $n^{2}$ for an obvious reason I am not seeing ?

  • $\begingroup$ Could you explain the model in more detail? Like what inputs do Alice and Bob receive, and whether this is randomized or deterministic (or quantum)? $\endgroup$ – Robin Kothari Oct 2 '10 at 23:57
  • $\begingroup$ I edited accordingly. I am interested on randomized or deterministic stuff (but not quantum), even if practically only the deterministic framework is of importance for me (I plan to use the result to prove LB on the size of an OBDD). $\endgroup$ – Sylvain Peyronnet Oct 3 '10 at 0:07
  • 1
    $\begingroup$ I think this is usually called one-way comm compl, as Bob is not allowed to send any bits to Alice in you model. $\endgroup$ – domotorp Oct 3 '10 at 6:54

There are $n^{n^2}$ binary operations on $S$. The question is how many of them are associative. Kleitman, Rothschild and Spencer give an asymptotic counting formula for this problem in their paper The number of semigroups of order $n$. It has a relatively simple form in what they call the "non-rare instances" where the peak of $f(t)$ dominates so the other terms can be neglected without affecting the asymptotics. You should be able to give a lower bound for your question by cranking through the math with this formula.

  • 1
    $\begingroup$ Thanks, I will look at this paper and I come back here to let you know. $\endgroup$ – Sylvain Peyronnet Oct 3 '10 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.