Communication complexity and association schemes

Let D₀,..., D_n be the {0,l}-matrices forming an association scheme. Since Σ_k=0ⁿD_k is the all-one matrix, a linear combination Σ_k=0 ⁿc_kD_k can be regarded as the matrix (f(x,y))_x,y representing the function f defined by f(x,y)=c _k if (x,y) is in relation corresponding to matrix D_k . Parameters of functions thus obtained may now be studied exploiting properties of the association scheme. One such parameter is the communication complexity C(f), which is the number of bits that two persons have to exchange in order to evaluate f(x,y), when initially one person only knows x and the other person only knows y