<p>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 <a href="http://www.jstor.org/pss/2041879">The number of semigroups of order $n$</a>. 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.</p>

CC BY-SA 2.5
2010-10-03T17:27:21.783Z
Thanks, I will look at this paper and I come back here to let you know.
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-03T00:56:12.930Z
2010-10-03T00:56:12.930Z
Per Vognsen
<p>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.</p>

<p>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$.</p>

<p>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})$.</p>

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

CC BY-SA 2.5
2010-10-02T23:57:19.110Z
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)?
Robin Kothari
CC BY-SA 2.5
2010-10-03T00:07:13.710Z
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).
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-03T06:54:07.783Z
I think this is usually called one-way comm compl, as Bob is not allowed to send any bits to Alice in you model.
domotorp
<cc.complexity-theory><communication-complexity>
Communication complexity for deciding associativity
Sylvain Peyronnet
# Communication complexity for deciding associativity

(Asked by: username_0 on 2010-10-02)

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 ?

**Tags:** cc.complexity-theory, communication-complexity
> **Comments:**
> **username_1**: 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)?  
> **username_0**: 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).  
> **username_2**: I think this is usually called one-way comm compl, as Bob is not allowed to send any bits to Alice in you model.  

---

## 1 answers

### Answer by username_3 on 2010-10-03. Score: 10 | Accepted answer

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$](http://www.jstor.org/pss/2041879). 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.

> **Comments:**
> **username_0**: Thanks, I will look at this paper and I come back here to let you know.  

---

