DocumentCode :
2383986
Title :
Communication complexity and association schemes
Author :
Tamm, Ulrich
Author_Institution :
Dept. of Math., Bielefeld Univ., Germany
fYear :
2000
fDate :
2000
Firstpage :
4
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
Type :
conf
DOI :
10.1109/ISIT.2000.866294
Filename :
866294
Link To Document :
بازگشت