Abstract :
Let D0,..., Dn be the {0,l}-matrices forming an association scheme. Since Σk=0nDk is the all-one matrix, a linear combination Σk=0 nckDk 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 Dk . 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
Keywords :
communication complexity; eigenvalues and eigenfunctions; information theory; matrix algebra; polynomials; all-one matrix; association schemes; communication complexity; eigenvalues; information theory; matrices; polynomials; Complexity theory; Computer science; Ear; Eigenvalues and eigenfunctions; Information theory; Mathematics; Polynomials;